# Need help constructing a Deterministic Finite Automata with AT MOST

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.

• possible duplicate of How to prove a language is regular? – D.W. Aug 1 '15 at 21:19
• 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. – Rick Decker Aug 1 '15 at 21:45
• @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. – Gana Aug 2 '15 at 2:13
• 0000 contains three pairs of zeroes, as @RickDecker's comment shows. – David Richerby Aug 2 '15 at 9:03

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.
• 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. – Corristo Aug 1 '15 at 19:34