3
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Another way to think of the property that might be easier to work with is that each one must be followed by at least two zeroes. $\endgroup$ – Luke Mathieson Aug 31 '13 at 3:18
  • $\begingroup$ @luke-mathieson To be slightly more precise, each $1$ neither in ultimate nor in penultimate position must be followed by at least two zeroes $\endgroup$ – J.-E. Pin Aug 31 '13 at 9:22
  • $\begingroup$ Luke's proposition together with some of our reference questions can indeed be helpful. $\endgroup$ – Raphael Sep 2 '13 at 9:58
2
$\begingroup$

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).

$\endgroup$

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.