# DFA for strings with number of 0's odd only in substring longer than 1

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

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

• 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) Jun 16 '18 at 20:58
• cs.stackexchange.com/q/1331/755
– 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.

• You cannot assume what $p$ is when using pumping lemma. Aug 14 '18 at 13:39