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 |
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |