I'm trying to design and DFA that accept string with an odd number of 0`s, but counting only the ones within sub-strings with two or more 0.

So, for example, 011000, will be accepted since it has 4 0`s, but only three or them are inside a sub-string of two or more. But 0001000, wont be accepted.

  • 1
    $\begingroup$ After processing any character, you go into a state that is a combination of (0, 1, 2 or more zeroes) x (even or odd number of zeroes counted) $\endgroup$
    – gnasher729
    Commented Jun 16, 2018 at 20:58
  • $\begingroup$ cs.stackexchange.com/q/1331/755 $\endgroup$
    – D.W.
    Commented Aug 14, 2018 at 20:29

1 Answer 1


I believe your language is not regular and if I'm not mistaken, the pumping lemma suffices: Let us assume by contradiction your language is regular, thus it should hold all 3 conditions of the pumping lemma.

Let $w=0^{2p+1}111$, notice $w\in L$ because $2n$ is always even, thus by adding $1$ we have an odd number of $0$s.

Now let us take a simple example where $p=1$, but this should work for any $p$.

In this case, $p=1$, notice $|w|>p$, since $|w|=5$, essentially $w=000111$. In our case this means $y=0$ and because $|xy|\le 1$ and because $|y|>0$ where 1 is our pumping length this means $x=\epsilon$.

This leaves $z=0011$. However, for $i=2$, we receive: 000011 which is $y^2z \equiv 000011 $.

Then the number of 0s in your substring is now even, meaning $000011 \notin L$. Again, we can do this for any pumping length $p$ by simply pumping up or pumping down.

Thus there won't be a DFA/NFA for that. You can try using a TM.

For more information: pumping lemma.

  • $\begingroup$ Perhaps some of the data was missing, making the language hold the conditions of the pumping lemma, let me know =) $\endgroup$ Commented Aug 14, 2018 at 13:14
  • $\begingroup$ You cannot assume what $p$ is when using pumping lemma. $\endgroup$
    – xskxzr
    Commented Aug 14, 2018 at 13:39
  • $\begingroup$ You're correct, thank you for your comment. However, for this is simply an example, I'll edit the answer to emphasize that. Regardless, for such a word, we could always then make the number of 0s be even using pumping. $\endgroup$ Commented Aug 14, 2018 at 14:42

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.