I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted.

the DFA is as such:

the dfa

The only language I could come up with that sort of covers this, is:

$L=\{w: \#_1(w)\geq 1 \; \& \; ends\;with\;even\;no.\;of\; '0'\;or\;ends\;with\;'1'\}$

yet this formulation for $L$ seems really off to me.

is there a better way to formulate this? or perhaps my answer is incorrect?


1 Answer 1


Your answer is correct. $L = \{ w \; | \; w \text{ has at least one 1 and ends with an even number of 0s or ends with a 1 } \;\}$

Sketch of Proof in one direction: Because there's at least one 1, somewhere we find a 1 and get to $q_2$. To end in $q_2$, either the last word was a 1; or it was zero and last state was $q_3$. Everytime we're in $q_3$, we have an odd number of zeros at the end.

  • $\begingroup$ This is an answer I went through, but the “length” of the definition felt odd to me, though I see the logic behind this definition. I suppose this is the correct answer indeed, thank you! $\endgroup$
    – Aishgadol
    Commented Jan 3 at 7:50
  • $\begingroup$ Its the same answer the asker suggested. $\endgroup$ Commented Jan 3 at 8:18

Your Answer

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

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