Running the automaton on an input, step by step

Simulating an automaton simply means following, letter by letter, the sequence of states it goes through while reading a given word - then looking at the final state to determine whether the word is accepted. Let's take again the automaton that recognizes words ending in «ab» (states q0 initial, q1, q2 accepting, transitions recalled in the previous lesson).

Let's simulate it on the word «baab»:

Simulation of «baab»   (q0 initial, q1, q2 accepting)

  letter read:         b        a        a        b
  state before:        q0       q0       q1       q1
  state after:         q0       q1       q1       q2

  final state = q2  ->  ACCEPTED (q2 is accepting)

At each step, we start from the current state, read the next letter, and the transition table gives the new state. Here, the final state after the four letters is q2, which IS accepting: the word «baab» is therefore accepted - and indeed, it does end in «ab».

Let's compare with the word «aba»:

Simulation of «aba»

  letter read:         a        b        a
  state before:        q0       q1       q2
  state after:         q1       q2       q1

  final state = q1  ->  REJECTED (q1 is not accepting)

This time the final state is q1, which is NOT accepting: the word «aba» is rejected. This is consistent, since «aba» ends in «ba», not «ab» - even though the word PASSED through the accepting state q2 just before the last letter.

Classic pitfall: stopping the simulation too early, as soon as the automaton reaches an accepting state, thinking "that's it, the word is accepted." This is wrong: the ENTIRE word must be read to the end, acceptance is decided only by the very last state reached.

Another pitfall, common early in learning: forgetting to reset the automaton to the initial state q0 before starting a new simulation. Each word is tested independently, always starting fresh from zero.