Select a Chapter: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Back to the Main Page
Chapter Twenty listings: 8 classes

public abstract class FiniteAutomaton
{
     public static final int ACCEPT = -1, REJECT = -2;
     public static final int q0 = 0, q1 = 1, q2 = 2, q3 = 3, 
               q4 = 4, q5 = 5, q6 = 6, q7 = 7, q8 = 8, q9 = 9;


     public String askOpinion (Sentence input)
     {    return accepts (input)  ?  "accepted"  :  "rejected";
     }    //======================


     public boolean accepts (Sentence input)
     {    int state = q0;
          while (state >= q0)
               state = nextState (state, input.next());
          return state == ACCEPT;
     }    //======================


     public abstract int nextState (int state, byte symbol);
}


public class Div2FA extends FiniteAutomaton
{
     /** Tell whether the base-four input is divisible by 2. */

     public int nextState (int state, byte symbol)
     {    return state == q0 ? (symbol == 0 ? q0 : symbol == 1 ? q1
                                : symbol == 2 ? q0 : symbol == 3 ? q1
                                : ACCEPT)
               : state == q1 ? (symbol == 0 ? q0 : symbol == 1 ? q1
                                : symbol == 2 ? q0 : symbol == 3 ? q1
                                : REJECT)
             : REJECT;  // should never happen
     }    //======================
}
//##############################################################


class Div2FAApp
{
     public static void main (String[] args)
     {    System.out.println 
                  (new Div2FA().askOpinion (new Sentence (args[0])));
     }    //======================
}


public class Sentence
{
     private String itsString;
     private int itsIndex = 0;
     private int itsBase = '0';


     public Sentence (String input)  // the natural constructor
     {    itsString = (input == null)  ?  ""  :  input;
          if (itsString.length > 0 && itsString.charAt (0) >= 'a')
               itsBase = 'a';
     }    //======================


     public Sentence()
     {    this (javax.swing.JOptionPane.showInputDialog
                          ("Enter a sentence for the FA"));
     }    //======================


     public Sentence (Sentence given)
     {    this ((given == null)  ?  ""  :  given.itsString);
     }    //======================


     public byte next()
     {    return (byte) ((itsIndex >= itsString.length)  ?  -1
                        :  itsString.charAt (itsIndex++) - itsBase);
     }    //======================
}


public class Div3FA extends FiniteAutomaton
{
     private final int NUM_SYMBOLS = 4;
     private final int NUM_STATES = 3;  // other than ACCEPT/REJECT
     private final int[][] del = { {q0, q1, q2, q0, ACCEPT},   //q0
                                   {q1, q2, q0, q1, REJECT},   //q1
                                   {q2, q0, q1, q2, REJECT} }; //q2


     /** Tell whether the base-four input is divisible by 3. */

     public int nextState (int state, byte symbol)
     {    return (state < 0 || state >= NUM_STATES) 
                  ? REJECT
                  : (symbol < 0 || symbol >= NUM_SYMBOLS) 
                           ?  del[state, NUM_SYMBOLS]  
                           :  del[state, symbol];
     }    //======================
}
//##############################################################


class Div3FAApp
{
     public static void main (String[] args)
     {    System.out.println 
                  (new Div3FA().askOpinion (new Sentence (args[0])));
     }    //======================
}


public abstract class TuringMachine
{
     public final boolean ACCEPT = true, REJECT = false;
     private final byte[] theRam = new byte[10000];
     private int thePos = 0;


     public String askOpinion (Sentence input)
     {    return accepts (input)  ?  "accepted"  :  "rejected";
     }    //======================


     public boolean accepts (Sentence input)
     {    if (input != null)
          {    theRam = new byte[10000];  // start with fresh input
               int k = 1;
               byte symbol = input.next();
               while (symbol >= 0)
               {    theRam[k++] = symbol;
                    symbol = input.next();
               }
               thePos = 0;
          }
          return start();
     }    //======================


     public byte head()
     {    return theRam[thePos];
     }    //======================


     public static void moveOn()
     {    thePos++;
     }    //======================


     public static void backUp()
     {    thePos--;
     }    //======================


     public static void moveOn (byte replacement)
     {    theRam[thePos++] = replacement;
     }    //======================


     public static void backUp (byte replacement)
     {    theRam[thePos--] = replacement;
     }    //======================


     public abstract boolean start();
}


public class Palindrome extends TuringMachine  // 6 states
{
     public boolean start()
     {    if (head() == -1)                                      //1
          {    moveOn();                                         //2
               return isPalindrome();                            //3
          }                                                      //4
          else // the current position has 0 or 1                //5
               return REJECT;                                    //6
     }    //======================


     public boolean isPalindrome()
     {    if (head() == 0)                                       //7
          {    moveOn (-1);                                      //8
               return findZeroAtOtherEnd();                      //9
          }else if (head() == 1)                                 //10
          {    moveOn (-1);                                      //11
               return findOneAtOtherEnd();                       //12
          }else                                                  //13
               return ACCEPT;                                    //14
     }    //======================


     public boolean findZeroAtOtherEnd()
     {    while (head() == 0 || head() == 1)                     //15
               moveOn();                                         //16
          backUp();                                              //17
          return shouldSeeZero();                                //18
     }    //======================


     public boolean shouldSeeZero()
     {    if (head() == 0)                                       //19
          {    backUp (-1);                                      //20
               return goToFront();                               //21
          }                                                      //22
          else                                                   //23
               return (head() == 1) ? REJECT : ACCEPT;           //24
     }    //======================


     public boolean goToFront()
     {    while (head() == 0 || head() == 1)                     //25
               backUp();                                         //26
          moveOn();                                              //27
          return isPalindrome();                                 //28
     }    //======================


     // the following two are left as exercises
     public boolean findOneAtOtherEnd()
     public boolean shouldSeeOne()
}


The LAMBDA symbol in the book may come through as E with dots over it in PDF.

1. BasicExpression  -->  Term  {AddOp  Term}
2. AddOp  -->  +  |  -  
3. Term  --> Factor  {MulOp  Factor}
4. MulOp  -->  *  |  /  |  % 
5. Factor  -->  ClassName  SimpleUnit  |  -  SimpleUnit  |  SimpleUnit  
6. SimpleUnit  -->   VariableOrMethodCall   |  Literal  |  (  Expression  )

7. Expression  -->  BoolTerm  {or  BoolTerm}  
                 |  when  Expression  ?  Expression  :  Expression
8. BoolTerm  -->  BoolFactor  {and  BoolFactor}
9. BoolFactor  -->  not  BasicExpression  Relational  |  BasicExpression  Relational
10. Relational  -->  <  BasicExpression  |  >  BasicExpression  
                  |  <=  BasicExpression |  >=  BasicExpression
                  |  ==  BasicExpression  |  <>  BasicExpression  |  /\

11. ModuleDeclaration  --> class  Name  extends  ClassName  {Declaration}  end
                         |  singleton  Name  {Declaration}  end
12. Declaration  -->  private  BasicDeclaration  |  BasicDeclaration
13. BasicDeclaration  -->  final  Type  Name  |  Type  Name
                        |  MethodHeading  {Statement}  end
                        |  new  ConstructorHeading  {Statement}  end
14. Type  -->  ClassName  {  [  ]  }  |  number  {  [  ]  }  |  boolean  {  [  ]  }
15. MethodHeading  -->  Name  (  VariableDeclarations  )  returns  ReturnType 
16. VariableDeclarations  -->  Type  Name  { ,  Type  Name}  |  /\
17. ReturnType  -->  Type  |  nothing
18. ConstructorHeading  -->  ClassName  (  VariableDeclarations  )
                          |  SingletonName  (  )

19. Statement  -->  Name  :=  Expression
                 |  VariableOrMethodCall  AssignmentPart
                 |  return  Expression
                 |  if  Expression  Alternatives
                 |  repeat  {Statement}  until  Expression
                 |  for  Name  :=  Expression  upto  Expression  do  {Statement}  end
20. AssignmentPart  -->  =  Expression  |  +=  Expression  |  -=  Expression  |  /\
21. Alternatives  -->  Statement  |  then  {Statement}  RestOfIf
22. RestOfIf  -->  elsif  {Statement}  RestOfIf  |  else  {Statement}  end  |  end

23. VariableOrMethodCall  -->  new  Type  RestOfConstruction  |  this  {Specifier}
                            |  SingletonName  .  BasicUnit  |  BasicUnit
24. RestOfConstruction  -->  Parameters  |  [  Expression  ]  {  [  Expression  ]  }
25. Parameters  -->  (  Arguments  )  |  /\
26. Arguments  -->  Expression  {  ,  Expression  }  |  /\
27. BasicUnit  --> VariableName  {Specifier}  |  MethodName  Parameters  {Specifier}
28. Specifier  -->  .  BasicUnit  |  [  Expression  ]  


     singleton Math
          final number PI
          private final number randomSeed  // used by Math.random()


          abs (number x)  returns number
               return when x >= 0  ?  x  :  -x
          end


          new Math ()  // for initializing field variables, etc.
               PI = 3.141593
               randomSeed = System.currentTimeMillis()
          end


          logInt (number base, number target) returns number // in Math
               if target <= 1 or base <= 0 return 0
               result := 0
               repeat
                    target = target / base
                    result += 1
               until target <= 1
               return target
          end
     end


     class ListOfStrings extends Object
          private number size
          private String[] item


          new ListOfStrings (number cap)  // constructor
               size = 0
               item = new String [when cap > 5 ? cap : 5]
          end


          isEmpty () returns boolean
               return size == 0
          end


          get (number index) returns String
               return when index < 0 or index >= this.size  
                                   ?  null  :  this.item[index]
          end


          add (String given) returns nothing
               if size < item.length then
                    item[size] = given
                    size += 1
               end
          end  // of add method


          contains (String given) returns boolean  // in ListOfStrings
               for k := 0 upto this.size do
                    if this.item[k].equals (given) return true
               end
               return false
          end


          toArray () returns String[]  // in ListOfStrings
               result := new String [this.size]
               for k := 0 upto this.size do
                    result[k] = this.item[k]
               end
               return result
          end
     end  // of ListOfStrings class

All information Copyright (c)1999 - Dr. William C. Jones, Jr.
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved.