Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
