Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

2
votes
3answers
190 views

What is the easiest way to determine the accepted language of a deterministic finite automaton (DFA)?

I'm new to automata theory and I'm currently working on some exercises on determining the accepted language of DFAs. I was wondering whether there exists some clever strategy to determine the accepted ...
1
vote
1answer
20 views

Transition function of the generalized nondeterministic finite automata

Why does the transition function of a GNFA map from two states to a regular expression $$ \delta: (Q \setminus \{q_{start}\}) \times (Q \setminus \{q_{accept}\}) \to R $$ instead of mapping from the ...
2
votes
2answers
27 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
0
votes
0answers
9 views

Where does $b(10)$ goes under this automaton

This is finite state automaton for Grigorchuk group. I have never studied automaton formally, so I wanna check is it fine the way I am doing it. Here $\epsilon$ change the first entry on string ...
2
votes
0answers
38 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
1
vote
1answer
41 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
1
vote
0answers
33 views

Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is ...
0
votes
1answer
25 views

How to prove the language of all binary numbers that are prime is nonregular using pumping lemma?

How to prove the language of all binary numbers that are prime is not regular using pumping lemma? I have seen Can an infinite set of primes be a regular language or CFG? We have not studied the ...
2
votes
2answers
247 views

how to prove that the following is not a regular language?

the language we want to disprove is : $$ L = \{ 0^i1^j| gcd(i,j)=1 \} $$ my attempt : i used the pumping lemma this way: consider the set of strings of the form $0^p1^q$ such that $n <=p$ and ...
1
vote
0answers
35 views

Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it. $L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$ Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$ For language $L':$ $M'=(Q', ...
-1
votes
1answer
19 views

How to construct a DFA for truncate the rightmost symbol from a given string?

If I have a truncate operation defined which removes the rightmost symbol from a string ,for instance I have a string say aababb so it removes the rightmost symbol b and the output is aabab. so how ...
2
votes
1answer
33 views

How can a Moore machine be converted into an equivalent Mealy machine and vice versa?

Moore machine is a finite-state machine whose output values are determined by its current state only. Mealy machine is a finite-state machine whose output values are determined both by its current ...
2
votes
0answers
58 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
1
vote
2answers
26 views

How to construct the DFA for the following question?

Given $L=\{ab^5 w b^4 \}$ where $w=\{a,b\}^*$. I am not able to construct it, I tried it but getting problems with the transitions for input symbol a.
0
votes
1answer
43 views

Learning finite automata from symbol set and given sample

Good day. We have a finite automaton F1, for example, . We need to get automaton F2 that accepts strings like accepted by ...
2
votes
1answer
40 views

NFA to DFA and Regular Expression

The truth is that my teacher gave us a homework, and I wanted to ask you if I did this right. What I have to do is answer the following questions given the following NFA. Why is this an NFA? What ...
1
vote
0answers
53 views

nth-root of continued fraction with Raney transducers

There are some algorithms for doing basic arithmetic by using regular continued fraction expansions. These algorithms are mainly due to Gosper (1972) and Raney (1973). These two approaches use ...
0
votes
1answer
53 views

Pushdown Automata formal definition, L(M), tracing input

Let M be a deterministic PDA with the transition function d: ...
2
votes
1answer
18 views

Languages and their relation : help

This is not a homework question though, this is something I wish to know to add to my own knowledge. While reading one of the texts on automata (K.L.P. Mishra, "Theory of Computer Science : Automata, ...
2
votes
1answer
30 views

Show that the function floor-log is primitive recursive

I have been stuck on this problem for a while and I was hoping someone could help me with it. This is for my computer science automata and formal languages class. Given an integer $b$ greater than or ...
0
votes
1answer
29 views

Push Down Automata

I've been stuck on this one problem for a couple of days now with no clue on how to complete it. Construct a PDA which accepts precisely the language $\{a^{2n} (bc)^n\mid n \in \mathbb{N}\}$. ...
0
votes
1answer
37 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
0
votes
0answers
16 views

How to prove that Pumping lemma can't be used to prove regular languages.

I need a prove that pumping lemma can't be used to prove regular language. Pumping lemma is only used for proving non-regular language, but I need to show that how it can't be used to prove regular ...
-1
votes
2answers
30 views

How to Solve Complex Non-Regular Language? [closed]

$L_5={\{ c^n a^m b^p,n+m=p,p≥6}\}$ where $∑=(a,b,c)$ I need little help, I was practicing Pumping lemma, and I encountered this language, I saw these conditions and I got totally confused, what to do ...
0
votes
1answer
19 views

Are these languages Regular or Non-regular?

I have these two languages $L={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
1
vote
2answers
41 views

Why |w|>=m in pumping lemma?

If L is a regular language, then there exists a constant n (which depends on L) such that ...
0
votes
1answer
21 views

Why does this concatenation doesn't work for these 2 dfa's [closed]

I have the following deterministic finite automaton which accepts an even number of 0's. and this automaton which accepts an odd number of 1's: I want to concatenate these 2 automatons. I ...
1
vote
1answer
20 views

Two DFA to one NFA.

Let assume that I have given DFA $D$ which recognize language $L$. Now I would like create the DFA/NFA which recognize the language $L'$. $$ L' = \{ w \in L : |w| = 2k, k \ge 0 \}$$ In words, $L'$ ...
0
votes
0answers
26 views

Theory automata. Proof. [duplicate]

Let $A/B= \{ w : wx \in A \}$ for some $x \in B $. Show that if $A$ is regular and $B$ is any language, then $A/B$ is regular. Please hint me with doing it using Myhill-Nerod's theorem. I observed ...
-1
votes
2answers
24 views

Decomposing an infinite regular language

Let $L$ be an infinite regular language. Prove that $L$ can be split up into $L_1, L_2$, so that $L_1 \cup L_2 = L$ and $L_1 \cap L_2 = \emptyset$ Can you give me some directions to do it? Thanks ...
0
votes
0answers
29 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
1
vote
1answer
32 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
1
vote
2answers
32 views

Convert NFA to DFA

I have to convert the following NFA's into the equivalent DFA's. I have done the following: Could you tell me if it is correct??
0
votes
2answers
33 views

Finding the regular expression

I have the problem below: I need to find the regular expression of the set of strings where $n(a)+n(b)$ is an even number (where $n(a)$ is the number of $a$'s and $n(b)$ is the number of $b$'s) .. I ...
-1
votes
1answer
25 views

Automata accepting

Let $A = \{ a,b\} $ and $ L = \{ w \in A^* : |a| = 2k+1, |b| = 2l, k,l \ge 0 \}$ $|a| = 2k+1 $ means that amount of 'a' in word $w$ should be odd. I am asking for any advice. I tried do it a lot of ...
1
vote
1answer
44 views

Regular expressions

I have this assignment and I have to prove that $$ (b+aa^* b)+(b+aa^* b)(a+ba^* b)^* (a+ba^* b) = a^* b(a+ba^* a)b^* $$ How do I prove this? What I have is this: $$\begin{align} \text{LHS} ...
-1
votes
1answer
32 views

Show that every recursively enumerable set is accepted by a Turing machine with only two non accepting states and one accepting state.

A recursively enumerable set is a set where you can write a program that will output each element in the set: E1, E2, E3... it's okay if this program never stops. For more info look here : ...
0
votes
1answer
29 views

Closure of regular languages, Star Operator

Show with a counterexample that the following construction doesn't prove the closure of regular languages at the concatenation. In other words, find a NFA $N_1$ such that the NFA $N$ of the ...
0
votes
1answer
25 views

the minimal deterministic finite automaton recognizing $\{1^n 0^n /n\leq N\}$

Given a language $L$ how can I determine the number of states of the minimal automate which recognizes $L$. I want some examples and to understand the methods that we can use to find a lower bound for ...
0
votes
1answer
55 views

Prove that $A/B$ is regular when $A$ is regular and $B$ is regular or not regular.

Prove that $A/B$ is regular when $A$ is regular and $B$ is regular or not regular. $$A/B=\{w: wx\in A\ \text { for some }\ x\in B\}$$ Please give me a clue.
2
votes
0answers
34 views

show that language is regular

Let $B_n = \{a^k\ |\text{ where } k\text{ is a multiple of } n\}$. Show that for each $n\ge 1$ the $B_n$ language is regular. My proposition of solution: What about it ?
1
vote
3answers
49 views

Show that a language is regular

Show that language $B$ is regular: $$B = \left\{1^ky\mid y\in \{0,1\}^*\right\} $$ $y$ contains $\ge k$ symbols $1$ So I try in following way - I'll draw DFA: What about my solution? Is it good?
0
votes
0answers
33 views

Intersection of 2 deterministic finite state automata, but nondeterministically

Starting from 2 simple deterministic finite state automata, I need to construct a non-deterministic automaton that accepts the intersection of the two inputs. Using the algorithm presented at ...
1
vote
2answers
53 views

What the way studying math to automata theory

Good day everyone. I need to know automata theory. Can you advice me the best way to study math? What themes will I need to know to understand automata theory. What a sequence of study? What level ...
3
votes
0answers
71 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, ...
1
vote
1answer
34 views

Is the empty set/language contained in the following set

Assume I have the following set of languages: $$ \{L \subseteq \{0,1\}^* \mid \text{for all $w \in L$, $|w| \leqslant 3$}\} $$ I know it contains the language containing the empty word since the ...
0
votes
0answers
105 views

Automata to detect numbers divisible by $7$

I have a task and I really have no idea how to solve it. Build deterministic finite automata such that it can detect numbers divisible by $7$. So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ ...
1
vote
1answer
33 views

Show that the language is regular - Closure

For languages $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language $$L=\{w \ \mid \ w=a_1 b_1 \dots a_k b_k, \text{ where } a_1 \cdots a_k \in A \text{ and } b_1 \cdots b_k \in B, ...
0
votes
1answer
31 views

Show that the language is regular

Let $$B_n=\{a^k \ \mid \ k \text{ is a multiple of } n\}$$ Show that for each $n \geq 1$, the language $B_n$ is regular. $$$$ Could you give me some hints how we coukd show this?? Do we have ...
0
votes
1answer
24 views

Construct the DFA of the language

I have to construct a DFA for the language $$\{w \mid w \text{ has exactly two } a's \text{ and at leat two } b's\}$$ To construct it we have to construct first the DFA's for the languages $$\{ w ...