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 Jun 16 '18 at 20:58
  • $\begingroup$ cs.stackexchange.com/q/1331/755 $\endgroup$ – D.W. Aug 14 '18 at 20:29

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.

| cite | improve this answer | |
  • $\begingroup$ Perhaps some of the data was missing, making the language hold the conditions of the pumping lemma, let me know =) $\endgroup$ – Reckless Engineer Aug 14 '18 at 13:14
  • $\begingroup$ You cannot assume what $p$ is when using pumping lemma. $\endgroup$ – xskxzr Aug 14 '18 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$ – Reckless Engineer Aug 14 '18 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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