3
$\begingroup$

I am stuck with constructing an DFA that has at most in it.

The question I am stuck with is:

Design an DFA that accepts all strings over {0, 1} that contain at most two 00’s and at most three 11’s as a substring.

An answer in a form of a graph would be perfect but if someone can explain in plain words, I will appreciate that as well.

$\endgroup$

migrated from stackoverflow.com Aug 1 '15 at 13:13

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ possible duplicate of How to prove a language is regular? $\endgroup$ – D.W. Aug 1 '15 at 21:19
  • $\begingroup$ As @vonbrand said, this is a sadistic problem, if for no other reason than we should presumably reject a string that contains 0000, since it contains 00xx, x00x, and xx00. $\endgroup$ – Rick Decker Aug 1 '15 at 21:45
  • $\begingroup$ @RickDecker Why would we reject a string that contains 0000? The questions says that it can contain at most two pairs of 00's so 0000 should be accepted, right? For example, a string such as 10011001 will also be accepted. At least, that is what I understand from the question. $\endgroup$ – Gana Aug 2 '15 at 2:13
  • 1
    $\begingroup$ 0000 contains three pairs of zeroes, as @RickDecker's comment shows. $\endgroup$ – David Richerby Aug 2 '15 at 9:03
2
$\begingroup$

You can use states of the form $(i,j)$ where $i$ counts the number of 00s and $j$ counts the numbers of 11s read so far.

$\endgroup$
  • $\begingroup$ How can this be translated into a diagram? $\endgroup$ – Gana Aug 1 '15 at 17:44
  • 1
    $\begingroup$ In order to detect a substring 00 or 11 you need to know the last character as well. So introducing states $(i,j)_x$ denoting that the last character read was $x$, you just have to define the transitions accordingly: $$\delta( (i,j)_0, 0) = (i+1, j)_0, \delta ((i,j)_0, 1) = (i,j)_1 \\ \delta((i,j)_1,0) = (i,j)_0, \delta((i,j)_1,1) = (i, j+1)_1 $$ Of course you have to include an initial state which is not of this form (you have not read a character yet) and an error state. $\endgroup$ – Corristo Aug 1 '15 at 19:34
1
$\begingroup$

This is a sadistic question...

It is easy to build a DFA over a, b for "at most 2 a" or "at most 3 b"; and build a DFA for the intersection (states are pairs of states, one of each automaton; transitions trace the first automaton in the first part of the state and of the second similarly; final states are composed of final states for both).

The same ideas (more complicated, but similar) give "at most two 00" or "at most three 11", and then build the intersection.

$\endgroup$
  • $\begingroup$ I'm not sure if I understand what you mean... Could you elaborate and maybe give some examples? $\endgroup$ – Gana Aug 1 '15 at 17:44

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.