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


See below.

Recognizing a String

Diagram of an automaton

If the LAST character of the string causes a transition to a FINAL state, then the string is recognized (accepted). Any thing else, and the string is not recognized (is rejected).

Here are the ways in which a string might be rejected:

  1. Too few characters to reach the final state.
  2. No state transition out of the current state for the current character:
    • The current state might be a non-final state with no transition for the current character.
    • The current state might be a final state, but there may be one or more characters left in the string but no transition for the current character.

As the string is processed, a final state might be reached several times. Final states can have transitions out of them. The automaton does not have to stop when it reaches a final state. What is required is for the last character of the string to lead to a final state.


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

Is the input string recognized?