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

  • $\begingroup$ 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. $\endgroup$ Feb 13 at 2:17
  • $\begingroup$ @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. $\endgroup$ Feb 13 at 3:25
  • $\begingroup$ 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. $\endgroup$ Feb 13 at 3:27
  • 1
    $\begingroup$ @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.) $\endgroup$ Feb 13 at 3:31

1 Answer 1


There are two types of people, those who allow missing transitions when defining a DFA, and those who do not. It does not make a notable difference, see my answer here. Stick to the definition you've seen in class/book/whatever.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.