The constructor should construct and initialize the tables.
Every cell of the transition table is initialized to "reject".
Particular transitions are added using the addTrans()
method.
Final states are added using the addFinal()
method.
Here is a complete implementation:
import java.util.Scanner; class FSATable { final int reject = -1 ; // state number for the reject state of the automaton final int asciiMin = 32 ; // ascii code for space character: first printable final int asciiMax = 127 ; // ascii code for DEL character: last printable private int numStates = 0 ; // states are numbered 0..numStates-1 private int[][] transition ; // one row per state, one column per character private int numFinal = 0; // valid final states are indexed 0..numFinal-1 private int[] finalStates ; // array of final states public FSATable( int numState, int numFinal) { numStates = numState ; // Each state gets its own row. // each row shows the next state, for each ascii // bit pattern 0..255 transition = new int[numStates][asciiMax+1] ; // Initialize the array of final states finalStates = new int[ numFinal ] ; // initialize all states to reject for ( int s=0; s<numStates; s++ ) for (int j=0; j<asciiMax; j++ ) transition[s][j] = reject ; } public void addTrans( int currentState, char input, int nextState ) { if ( currentState>=0 && currentState<numStates && nextState >=0 && nextState <numStates && input>=asciiMin && input <=asciiMax ) { transition[currentState][input] = nextState ; } else System.out.println("Problem with the transition: " + currentState + " reading " + input + " -> " + nextState ); } public void addFinal( int state ) { if ( numFinal >= finalStates.length-1 ) { System.out.println("No room for final state:" + state ); return; } finalStates[numFinal] = state; numFinal++ ; } /* search for a final state in the list of final states */ private boolean isFinal( int state ) { int j; for ( j=0; j<numFinal; j++ ) if ( state==finalStates[j] ) return true; return false; } public boolean recognize(String str) { int state = 0; // the current state int index=0; // index of the current character char current; // the current character // continue while there are input characters // and the reject state has not been reached while ( index < str.length() && state != reject ) { current = str.charAt( index++ ) ; state = transition[state][current] ; } // if the final state is reached with the last character, // the string is accepted. if ( index == str.length() && isFinal( state ) ) return true; else return false; } } public class FSATableTester { public static void main (String[] args) { FSATable fsa = new FSATable(5, 3); fsa.addFinal(2); fsa.addTrans( 0, 'a', 1 ); fsa.addTrans( 1, 'b', 0 ); fsa.addTrans( 1, 'c', 2 ); fsa.addTrans( 2, 'c', 2 ); String str; Scanner scan = new Scanner( System.in ); System.out.print("Enter a string -->"); while ( !((str = scan.nextLine()).equals("")) ) { if ( fsa.recognize( str ) ) System.out.println("The string is recognized."); else System.out.println("The string \"" + str + "\" is rejected."); System.out.print("Enter a string -->"); } } }
What input causes main()
to stop looping?