Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But I just cannot derive Sipser's language from what I have obtained. Any help at all would be appreciated.


1 Answer 1


The automaton is deterministic, so any string over $\{0,1\}$ has a unique path.

We need at least one $1$ to move from $q_1$ to the component where is the accepting state.

Immediately after reading $1$ we are always in accepting state $q_2$.

Look at the last $1$ in the input. At that moment we accept in $q_2$. To return to the accepting state, only reading $0$'s, we need an even number of $0$'s.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.