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:

• Represent the current state of the automaton with an integer held in a variable called state.
• Implement transitions between states by changing the number in this variable.
• Implement each state transition using an if or an else if statement.

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;

      . . . . . .

      else 
        state = reject ;


    }

  }