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


Finite Automaton

(My symbol for the "reject" state is not official.)

State Variable

You can translate a deterministic finite state automaton into a Java method almost mechanically. Experienced programmers use this trick frequently. When you know the trick, you will see that many problems involve an automaton. Writing the program will be routine.

The essential idea:

Java does not actually have an else if statement. What is called an else if statement is a method of indenting ordinary if and else statements so that each of many options is at the same level of indenting. This is extremely useful. The following fragment shows how this is done. Refer to the automaton as you study it.

  public boolean recognize(String str)
    final int reject = 3;
    int  state = 0;
    char current;

    while ( ... )
      current = next character in the string;

      // State 0
      if      ( state==0 && current=='a' )
        state = 1;

      // State 1
      else if ( state==1  && current >= 'a' && current <= 'y')
        state = 1;

      else if ( state==1  && current == 'z')
        state = 2;

      . . . . . .

        state = reject ;




If the current character is not accepted by the current state, a transition is made to the reject state. How is this implemented?