[Solved]: DFA drawing for binary string with substrings of minimum length 3 with at least two zeroes in each substring

Problem Detail: 

In trying to gain a better understanding of finite state machines, I stumbled across this idea and have been confused as to how to approach this case in terms of a DFA.

The set of binary strings of length at least 3 where every substring of length 3 contains at least two 0s.

So in other words, something like 100100010 should be in the language (L) for this DFA but something like 11001010 would not be in the language.

I know that you can start off by writing/drawing smaller DFAs for the substrings that are the pattern 000, 010, 100, 001, etc, but I cannot seem to get a hold of how it should look all together.

Any help in understanding this would be appreciated.

Asked By : rsxjan

Answered By : J.-E. Pin

The condition that all words have length $\geqslant 3$ makes the computation of the minimal DFA much more difficult. Thus let us first consider the language $$ K = \{ u \in A^* \mid \text{every substring of length 3 of $u$ contains at least two $0$} \} $$ where $A = \{0,1\}$. The forbidden patterns of the words of $K$ are $11$ and $101$, so that $K$ is the complement of the language $A^*(11 + 101)A^*$. But there is a nicer way to write $K$, using the comment of Luke Mathieson. Indeed, apart from the last two letters, every $1$ has to be followed by two $0$. This leads to the regular expression $K = (0 + 100)^*(\varepsilon + 1 + 10)$. I let you compute the minimal DFA of $K$ which has only three states (plus a sink state if you want a complete DFA).

Now $L = A^3A^* \cap K$ and you can use standard algorithms to get its minimal DFA (9 states, 10 if you count the sink state).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14050