Diagram of an automaton: circles and labeled arrows

The diagram is the central tool for understanding an automaton at a glance. The convention is universal: each state is drawn as a circle, each transition as an arrow labeled with the letter that triggers it, the initial state receives an incoming arrow that comes from nowhere, and an accepting state is distinguished by a double circle.

Let's take a concrete example: an automaton that recognizes exactly the words (over the alphabet {a, b}) that END with «ab». Three states are enough:

• q0: initial state, nothing useful read yet;
• q1: the last character read is an «a» (good start of the pattern);
• q2: the last two characters read are «a» then «b» - pattern found, accepting state.

Automaton: words that end with «ab»   (alphabet: a, b)

   initial state                            accepting state
        |                                        ^
        v            a               b           |
  -->  (q0)  --------------> (q1)  --------------> (( q2 ))
        ^                       |
        |           a           |
        +-----------------------+   (loop: q1 -> q1 upon reading «a»)

  (the other transitions - q2 -> q1 on «a», q2 -> q0 on «b»,
   q0 -> q0 on «b» - are grouped in the table below)

Complete transition table:
  state     on «a»             on «b»
  q0        goes to q1         stays in q0
  q1        stays in q1        goes to q2
  q2        goes to q1         goes to q0

Legend:  --> (q0) = initial state   |   (( q2 )) = accepting state (double circle)

Pay close attention to the return loops: from q1, if another «a» is read, it stays in q1 (nothing is lost); from q2, if another «a» is read, it goes back down to q1 (it starts watching for a new «ab» again); and a «b» from q0 or q2 brings it back to q0 (a «b» alone can never start the pattern).

Classic pitfall: forgetting a transition. A complete DFA must have EXACTLY one outgoing arrow per letter of the alphabet, for each state - even when it "seems obviously useless," like the return to q0 from q2 on a «b». An incomplete diagram does not describe a valid DFA.

Another pitfall: believing that a word is accepted as soon as it PASSES through the accepting state. The word «aba» passes through q2 after «ab», but ends in q1 after the last «a»: it is therefore rejected, since only the very last state counts.