A finite automaton that accepts at least three $a$s and at least two $b$s.

Question

I am trying to draw a DFA that accepts all strings over $\{a,b\}$ that have at least three $a$s and at least two $b$s. The image below is what I have come up with but it only works on some sequences. (It works with $aaabb$ but not with $bbaaa$.)

Answer 1

You have essentially represented the first three $a$'s as state, and the first two $b$'s; but, you aren't tracking both at the same time, so that state for $b$'s doesn't start accumulating until you've hit all three $a$'s.

So, why not consider having nodes representing the full collection of state short of the requirement? That is, have nodes representing the number of $a$'s and $b$'s, respectively, being $(0,0)$, $(1,0)$, $(2,0)$, $(0, 1)$, $(1,1)$, and $(2,1)$?

You'll also need nodes for "I have enough $a$'s, but only $x$ $b$'s" and vice versa; if you have enough $a$'s, adding another $a$ will just keep you in place.

Finally, you'll reach the "I have enough $a$'s AND enough $b$'s" state, from which you have three choices: $a$, $b$, or end.

Answer 2

This is essentially the answer given by Nick Peterson above but explained in a somewhat different manner.

First you need to identify the states the DFA can have. The DFA reaches the final state when it processes a string with at least three $a$'s and two $b$'s and stays there for any further inputs. Denote this state by $q_{32}$. But before reaching the state $q_{32}$, what possible states will the DFA have to pass through? It may have seen at least two $a$'s and two $b$'s (thus passing through state $q_{22}$) or three $a$'s and one $b$ (state $q_{31}$). Now repeat the same process for each of the states $q_{22}$ and $q_{31}$. For example, before $q_{22}$, the DFA could have been in states $q_{21}$ or $q_{12}$. Now if you do this correctly, then you would find twelve states:

$$q_{00}$$ $$q_{10}, q_{01}$$ $$q_{20}, q_{11}, q_{02}$$ $$q_{30}, q_{21}, q_{12}$$ $$q_{22}, q_{31}$$ $$q_{32}$$

Finally, you have to figure out the transitions happening at each of the states for inputs $a$ and $b$. For example, when DFA is in state $q_{20}$ and gets an input $a$, it transitions to state $q_{30}$; if it gets an input $b$, it goes to state $q_{21}$. You now have everything to draw the DFA.