# Provide a 2-state DFA for L={a}∗{b}∗ , the set of words of the form aa⋯abb⋯b

I'm kinda confused on how to construct this DFA. I'm trying but keep running into the problem of reading an a after the b's or what to do if starting with a 'b'.

• Remember that DFA can be “incomplete”, i.e., there can be states where there aren't outgoing transitions for all letters. If the automaton reaches such a state and there is no transition for the next letter, the computation stops and the word is rejected. Feb 13 at 2:17
• @JeanAbouSamra Well, technically a DFA is defined such that each state must have exactly one transition for each letter in the alphabet. So what you claim isn’t necessarily true for a DFA. Feb 13 at 3:25
• If you read a b before reading an a, you can go to a so-called “sink state” that is a non-accept state. In this state, there is a self-loop for both a and b. The same goes for reading a b after seeing at least one a. Feb 13 at 3:27
• @codeing_monkey Not really. The term “DFA” is ambiguous. Some require DFAs to be complete, some don't and call “complete DFAs” those which are. However, as OP was asked for a 2-state DFA, we can assume that the definition they are working with allows DFA to be incomplete. (The minimal complete DFA for that language has 3 states, but the minimal incomplete DFA, obtained by removing the sink state, achieves the requirement of 2 states.) Feb 13 at 3:31