go to previous page   go to home page   go to next page

Is there a transition out of the current state (in the diagram) that corresponds to the current character?


Yes. See the new diagram.

Final State

Diagram of an automaton

State transitions go in only one direction. In the example, there is a transition from state q0 to q1, but no transition from state q1 to q0. It is OK to have a transition back to a previous state, but the transition must be explicit.

Each character in the string may be used only once. A character may be used only if there is a state transition out of the current state that is labeled with the character. The input characters are used one by one to change the automaton from state to state. (Sometimes people say that a character has been "consumed" when it has been used to make a state transition).

The goal is to reach the final state with the last character of the string. The final state is indicated with double circles. An automaton can have many final states. (This example automaton has only one final state.)


Make the next state transition, as directed by the current character.