# Questions tagged [automata]

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

1,552 questions
1answer
40 views

### Proving $\sum_{i=1}^{n-1} i(i+1) = \frac{n(n-1)(n+1)}{3}$ for integer $n\geq 2$ [closed]

Prove the following inequality: $$\sum_{i=1}^{n-1} i(i+1) = \frac{n(n-1)(n+1)}{3}$$ for all integers $n\geq 2$ I used induction: base case and I.H I did the following: Prove by mathematical ...
1answer
28 views

1answer
36 views

### NFA with ε-moves.How to remove epsilon moves and do NFA [closed]

Can someone explain me how to removes ε-moves and do NFA automata.I want to know how it works for each examples.I must see wchich state i reached for ε-moves? But how to do that? There is algorithm on ...
0answers
36 views

### Closure of regular languages to $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$

Given: $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$ Given $L \subseteq\{0,1\}^*$, Prove/Disprove: If $L$ is regular $\implies$ $A(L)$ is regular If $L$ is context free$\implies$ $A(L)$ ...
0answers
37 views

1answer
30 views

### The formal language $L$ is regular iff there is a “reduced” NFA

I would appreciate some help for the following exercise: $L$ is a regular language if and only if there is a "reduced" NFA $N=\langle Q,A,\Delta, q_0,F\rangle$ with $L=L(N)$. With reduced I mean ...
1answer
28 views

### How to interpret the following DFA's language?

I'm reviewing material for a class I'm retaking before I take it again, and the teacher's homeworks are incredibly cryptic and the class notes aren't very exhaustive. I have a pretty good ...
1answer
35 views

### Finding the equivalence classes of a singleton set

Given a set L which contains only the string s = 10100, I need to find the equivalence classes [t], where t is a string that is not a prefix of s. (Σ = { 0, 1 }). I've drawn the smallest DFA ...
1answer
38 views

### FA that accepts odd 1's and ends with 101

I have been trying to come up with a FA that accepts odd 1's and ends with 101, also leading zeros are allowed. So far I have this. Problem is as you can see it fails with the string ...
4answers
67 views

### The definition of the empty string.

Here I'm having some confusion on what exactly is the empty string $\epsilon$. I'm going to list some prerequisite definitions I have surrounding the string, so please correct them as necessary. I ...
1answer
25 views

### How can we modify the proof if the alphabet in $M_1$ and the alphabet in $M_2$ are not the same? (Regular Language, Sipser)

I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser. How can we modify the proof if the alphabet in $M_1$ and the alphabet in $M_2$ are not the same? We ...
1answer
25 views

### DFA construction - How to construct an automaton that contains either 0 or 1 occurrences of 010?

I can't seem to make it work. I think I managed to produce a solution when it's exactly one occurrence of 010 but not when it's at most one occurrence. Check out my automaton.
1answer
27 views

### regular language proof

Question: Prove that a finite language is a regular language. How would I go about solving this? I tried my own approach (below) but didn't get far because I don't understand how I am supposed to ...
1answer
36 views

### DFM accepting sum of ab* and ba*

I have a problem with task: Draw a diagram of the deterministic finite state machine accepting the sum of languages marked with regular expressions ab* and ba*. I resolve task: Draw a diagram of the ...
1answer
111 views

### Gcd is a Regular Language [closed]

Show that GCD = {z|z = gcd(x,y), where x, y are binary numbers} is a regular language. [Hint: There is an algorithm that deals with 0s and 1s for this problem.]
1answer
36 views

### Does the empty string share properties of both zero and $\emptyset$?

I'm confused by the use of the empty string as the author uses it below. This is a excerpt from Introduction to the Theory of Computation by Sipser. Regarding the emptystring line, is this how ...
1answer
44 views

### DFM symbol a occurs twice

Let the L language over the alphabet {a, b, c} consist exactly of all words in which the symbol a occurs at least twice. Draw a diagram of the deteminist state-finite automaton accepting L and provide ...
0answers
35 views

### Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.
2answers
62 views

### context free language prove or disprove

I have to prove or disprove that for every language $L$ which has the properties: for every non-prime length there is at least one word in L. for every prime length none of the words are in L. is ...
1answer
42 views

### Give a state diagram for an NFA whose language L = …

L = {w ∈ {0,1,2} *: w is a ternary representation of an integer that is a multiple of 3 but not a multiple of 9} I've written a DFA accepting multiples of 3, but I'm not sure how I should proceed. ...
1answer
59 views

### Create NFA where the second symbol of the string is the same with the last symbol

I have tried: Let $L= \{a,b,c,d, \dots, z\}$. Create NFA where the second symbol of the string is the same with the last symbol. How do I solve this? Should I do repeatedly until $z$?
1answer
38 views

### If a language and its complement are context-free, is it regular?

If both $L$ and $\overline{L}$ are context-free, is $L$ necessarily regular?
1answer
37 views

### Language of this finite state automaton?

What would be the formal definition of the language for the following Finite State Automaton?
1answer
165 views

### Design DFA to check even number of 1s using 2 states.

The alphabet is {0,1}. Zero 1s in the string should be rejected. This can be done easily using 3 states. Can this be done usinng 2 states?
2answers
59 views

### Try finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]

"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
0answers
55 views

### Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R i am looking for the simplest solution- using a known languages that do not demand another formal proof.