package finiteAutomata;
/**
* Nondeterministic Finite Automaton.
*
* <BR><BR>An nfa has a non-empty, finite set of states Q; an alphabet S;
* a transition function d which maps Q x (S U {epsilon}) to P(Q); a
* unique "start" state; and zero or more "final" states. Notice that in
* an nfa, there can be zero, one, two, or multiple transitions from a
* given state on a given alphabet symbol, and epsilon transitions are
* also allowed (transitioning without processing an input symbol). The
* language L which is accepted by the nfa is the set of all strings s
* in S* which direct the nfa from "start" to any "final" state along at
* least one branch of the computation entailed by the transition function
* d. Though nfas seem quite different from dfas, it is a fact that they
* have no additional expressive power: every nfa has an equivalent dfa
* (a dfa which accepts the same language).
*
* <BR><BR>Data Fields:
* NFA states are labelled 0, 1, 2, etc., where state 0 is always
* the start state. There are data fields "numStates" for recording the
* number of states in the NFA, and "alpha" for storing the NFA's alphabet
* of input symbols. Final states are indicated with a boolean array,
* "isFinal".
*
* <BR><BR>With n states and m alphabet symbols, there are n x m possible
* inputs to the transition function (not counting epsilon transitions).
* An output from the transition function has to specify a list of zero
* or more destination states; we will represent this output with a
* 1-dimensional boolean array where "true" values indicate valid
* transitions. Thus, each NFA has a 3-dimensional boolean "transition"
* array: for each possible "from" state i, for each possible "to" state
* j, for the kth alphabet symbol, transition[i][j][k] is "true" iff we
* can transition from state i to state j on the kth alphabet symbol.
* Epsilon transitions are recorded in a separate boolean array:
* epsilon[i][j] is true iff we can transition from state i to state j
* on epsilon.
*
* <BR><BR>Each NFA has an equivalent DFA "D" whose states are a
* subset of the power set of {0,1,2,3,...,numStates-1}. Computations
* on the NFA are simulated by the corresponding computations on the
* equivalent DFA.
*
* @author Barbara Wahl
* @version Fall 2007
*/
public class NFA {
// ** DATA FIELDS **
/**
* number of states (positive)
*/
protected int numStates;
/**
* input symbols
*/
protected Alphabet alpha;
/**
* to indicate final states
*/
protected boolean[] isFinal;
/**
* for symbol-consuming transitions; transition[i][j][k]
* is true iff we can transition from state i to state j
* on the kth alphabet symbol.
*/
protected boolean[][][] transition;
/**
* for epsilon transitions; epsilon[i][j] is true iff
* we can transition from state i to state j on epsilon
*/
protected boolean[][] epsilon;
/**
* an equivalent DFA
*/
protected DFA D;
/**
* 0-parameter constructor. Uses console input to construct the
* NFA.
* @post constructs an NFA according to user's specifications
*/
public NFA()
{
// predefined = true if user wants to use a predefined NFA
boolean predefined = queryPredefined();
if(predefined)
predefinedDialog();
else
{ // get specs for user-defined DFA
numStates = queryNumStates(); // initialize numStates
queryAlphabet(); // initialize alpha
isFinal = new boolean[numStates]; // allocate isFinal array
queryFinal(); // initialize isFinal
// allocate the transition and epsilon arrays
transition = new boolean[numStates][numStates][alpha.size()];
epsilon = new boolean[numStates][numStates];
// run constructor menu
int choice = 0;
boolean done = false;
while(!done)
{
choice = constructorMenu();
done = constructorMenuHandler(choice);
}
}
D = this.convertToDFA();
System.out.println("\nYour NFA has been constructed as follows:");
this.printNFA();
// run testing menu, allowing user to change transitions,
// test strings, etc.
boolean done = false;
int choice;
while(!done)
{
choice = runMenu();
done = runMenuHandler(choice);
}
}
/**
* 5-parameter constructor.
* @param n number of desired states
* @param a input symbols
* @param t array of symbol-consuming transitions
* @param e array of epsilon transitions
* @param f array to indicate final states
* @pre n > 0
* @pre a is a non-null String of symbols with no whitespace
* or repeated characters
* @pre t is an array of size n x n x a.length()
* @pre e is an array of size n x n
* @pre f is an array of size n x 1
* @post constructs this NFA to have data fields as given by
* the arguments (arrays are deep-copied); initializes the dfa D
*/
public NFA(int n, String a, boolean[][][] t, boolean[][] e, boolean[] f)
{
Assert.pre(n>0, "n is positive");
numStates = n;
alpha = new Alphabet(a);
// allocate and initialize transition, epsilon, isFinal arrays
transition = new boolean[n][n][alpha.size()];
epsilon = new boolean[n][n];
isFinal = new boolean[n];
for(int i=0; i<n; i++)
{
isFinal[i] = f[i];
for(int j=0; j<n; j++)
{
epsilon[i][j] = e[i][j];
for(int k=0; k<alpha.size(); k++)
transition[i][j][k] = t[i][j][k];
}
}
// calculate equivalent DFA
D = this.convertToDFA();
}
/**
* Returns number of states.
* @return number of states in this NFA
*/
public int numStates()
{
return numStates;
}
/**
* Returns a copy of the Alphabet.
* @return alpha.toString()
*/
public Alphabet alpha()
{
return new Alphabet(alpha.toString());
}
/**
* Returns true if the given integer is in the correct range to be
* a state in this NFA.
* @param i the integer to be tested
* @return true iff 0 <= i < numStates
*/
public boolean validState(int i)
{
return (i>=0 && i<numStates);
}
/**
* Returns the set of final states.
* @return IntSet containing the state numbers of all final states.
*/
public IntSet getFinalSet()
{
IntSet finalSet = new IntSet();
for(int i=0; i<this.numStates; i++)
if(isFinal[i])
finalSet.add(i);
return finalSet;
}
/**
* Returns a copy of the symbol-consuming transition array.
* @return deep copy of this.transition
*/
public boolean[][][] transition()
{
boolean[][][] newTrans =
new boolean[numStates][numStates][alpha.size()];
for(int i=0; i<numStates; i++)
for(int j=0; j<numStates; j++)
for(int k=0; k<alpha.size(); k++)
newTrans[i][j][k] = transition[i][j][k];
return newTrans;
}
/**
* Returns a copy of the epsilon transition array.
* @return deep copy of this.epsilon
*/
public boolean[][] epsilon()
{
boolean[][] newEpsilon = new boolean[numStates][numStates];
for(int i=0; i<numStates; i++)
for(int j=0; j<numStates; j++)
newEpsilon[i][j] = epsilon[i][j];
return newEpsilon;
}
/**
* Returns a copy of the isFinal array.
* @return deep copy of this.isFinal
*/
public boolean[] isFinal()
{
boolean[] newFinal = new boolean[numStates];
System.arraycopy(isFinal,0,newFinal,0,numStates);
return newFinal;
}
/**
* Asks user if they want to use a pre-defined NFA.
* @return true iff user response begins with 'Y' or 'y'
*/
protected boolean queryPredefined()
{
System.out.print("Do you want to use a pre-defined NFA? Enter Y or N: ");
return Util.answerIsYes();
}
/**
* Queries user which of 4 pre-defined NFAs they will use.
* @post initializes this NFA to match user's choice of NFA
*/
protected void predefinedDialog()
{
int num;
while(true)
{
System.out.println("Choose a pre-defined NFA: ");
System.out.println(" 1 = Sipser, Figure 1.27");
System.out.println(" 2 = Sipser, Figure 1.31");
System.out.println(" 3 = Sipser, Figure 1.34");
System.out.println(" 4 = Sipser, Figure 1.36");
num = Util.readNum();
if(0 < num && num < 5)
break;
}
switch(num){
case 1:
constructN1();
break;
case 2:
constructN2();
break;
case 3:
constructN3();
break;
case 4:
constructN4();
break;
}
}
/**
* Prints constructor menu heading, and queries user until valid (positive)
* number of states is obtained.
* @return positive integer for numStates
*/
protected int queryNumStates()
{
int num = 0;
System.out.println("****** NFA CONSTRUCTOR MENU ****** " +
"\n Remember, state 0 is automatically the start state.");
while(num < 1) // query until valid num obtained
{
System.out.print(">> Enter a positive integer " +
"(number of states): ");
num = Util.readNum();
}
return num;
}
/**
* Queries user to obtain alphabet of input symbols.
* @post Alphabet of this NFA is initialized according to user response
*/
protected void queryAlphabet()
{
System.out.print(">> Enter a string with no spaces or repeated " +
"characters (alphabet): ");
alpha = new Alphabet(Util.readString());
}
/**
* Queries user to determine which states are final.
* @post isFinal array is initialized according to user responses
*/
protected void queryFinal()
{
for(int i=0; i<numStates; i++)
{
System.out.print(">> Enter true or false -- is state # "
+ i + " final? ");
isFinal[i] = Util.readBoolean();
}
}
/**
* Displays constructor menu options and prompts user to choose an
* action.
* @return valid choice number (1 thru 6)
*/
protected int constructorMenu()
{
int num;
while(true)
{
System.out.println("\nChoose an action: ");
System.out.println(" 1 = add a non-epsilon transition");
System.out.println(" 2 = add an epsilon transition");
System.out.println(" 3 = remove a non-epsilon transition");
System.out.println(" 4 = remove an epsilon transition");
System.out.println(" 5 = print current NFA");
System.out.println(" 6 = done constructing NFA");
num = Util.readNum();
if(num>0 && num<=6)
break;
else System.out.println("Try again!");
}
return num;
}
/**
* Takes action based on the provided constructor menu choice code.
* @param choice constructor menu choice code
* @return true iff user is done with menu options
* @pre 1 <= choice <= 6
*/
protected boolean constructorMenuHandler(int choice)
{
Assert.pre(1 <= choice && choice <= 6,
"1 <= choice <= 6");
switch (choice)
{
case 6: // done
return true;
case 5: // print
this.printNFA();
break;
case 4: // remove epsilon transition
removeEpsilonDialog();
break;
case 3: // remove non-epsilon transition
removeTransitionDialog();
break;
case 2: // add epsilon transition
addEpsilonDialog();
break;
case 1: // add non-epsilon transition
addTransitionDialog();
}
return false;
}
/**
* Displays run menu options and prompts user to make a choice of action.
* @return integer choice code (1 through 9)
*/
protected int runMenu()
{
boolean valid = false;
int choice = -1;
while(!valid)
{
System.out.println("\nChoose an action: ");
System.out.println(" 1 = change a transition");
System.out.println(" 2 = print this NFA");
System.out.println(" 3 = print the language of this NFA");
System.out.println(" 4 = test a non-empty string");
System.out.println(" 5 = test the epsilon string");
System.out.println(" 6 = print the equivalent DFA");
System.out.println(" 7 = pump a string on this NFA");
System.out.println(" 8 = replace this NFA with its"
+ " star closure");
System.out.println(" 9 = DONE with this NFA");
choice = Util.readNum();
if(1 <= choice && choice < 10)
valid = true;
}
return choice;
}
/**
* Takes action based on the provided run menu choice code.
* @param choice run menu choice code
* @return true iff user is done with menu options
* @pre 1 <= choice <= 9
*/
protected boolean runMenuHandler(int choice)
{
Assert.pre(1 <= choice && choice <= 9,
"1 <= choice <= 9");
int n;
switch (choice)
{
case 9: // "quit" from menu
System.out.println("Bye-bye!");
return true;
case 8: // replace this with this.starClosure()
this.starClosure();
break;
case 7: // "pump" a string
System.out.println("Enter an accepted string with length >= "
+ D.numStates);
D.pump(Util.readString());
break;
case 6: // print equiv dfa
D.printDFA();
break;
case 5: // test epsilon string
D.testEpsilonDialog();
break;
case 4: // test a non-epsilon string
D.testStringDialog();
break;
case 3: // print language
D.printLanguageDialog();
break;
case 2: // print
this.printNFA();
break;
case 1: // change a transition
n = changeTransitionDialog();
changeTransition(n);
}
return false;
}
/**
* Queries user regarding desired transition change.
* @return transition change choice code (1 through 4)
*/
protected int changeTransitionDialog()
{
int num;
while(true)
{
System.out.println("\nTo change a transition, " +
"choose an action: ");
System.out.println(" 1 = add a non-epsilon transition");
System.out.println(" 2 = add an epsilon transition");
System.out.println(" 3 = remove a non-epsilon transition");
System.out.println(" 4 = remove an epsilon transition");
num = Util.readNum();
if(num>0 && num<=4)
break;
else System.out.println("Try again!");
}
return num;
}
/**
* Takes action based on provided transition change choice code.
* @param n transition change choice code
* @post makes changes to transition array and re-calculates the
* equivalent DFA
*/
protected void changeTransition(int n)
// post: calls the appropriate transition-changing method
// and then re-calculates the equivalent DFA
{
switch(n)
{
case 4: // remove epsilon transition
removeEpsilonDialog(); break;
case 3: // remove non-epsilon transition
removeTransitionDialog(); break;
case 2: // add epsilon transition
addEpsilonDialog(); break;
case 1: // add non-epsilon transition
addTransitionDialog();
}
D = this.convertToDFA();
}
/**
* Queries user regarding which epsilon transition to remove.
* @post if user provides valid state numbers i and j,
* epsilon[i][j] is set to false and the equivalent DFA is
* re-calculated
*/
protected void removeEpsilonDialog()
{
int fromState, toState;
System.out.print("remove epsilon transition FROM state number: ");
fromState = Util.readNum();
System.out.print("remove epsilon transition TO state number:" );
toState = Util.readNum();
if(this.validState(fromState) && this.validState(toState))
{
epsilon[fromState][toState] = false;
D = this.convertToDFA(); // update the DFA
}
}
/**
* Queries user regarding which symbol-consuming transition to remove.
* @post if user provides valid state numbers i and j, and valid symbol
* s, the transition array is changed accordingly and the equivalent
* DFA is re-calculated
*/
protected void removeTransitionDialog()
{
int fromState, toState, index;
String symbol;
System.out.print("remove transition FROM state number: ");
fromState = Util.readNum();
System.out.print("remove transition TO state number: " );
toState = Util.readNum();
System.out.print("remove transition on SYMBOL: " );
symbol = Util.readString();
if(symbol.length()!=1)
return; // invalid symbol (not a single character)
index = alpha.indexOf(symbol.charAt(0));
if(index<0)
return; // invalid symbol (not in alphabet)
if(this.validState(fromState) && this.validState(toState))
{
transition[fromState][toState][index] = false;
D = this.convertToDFA(); // update the DFA
}
}
/**
* Queries user regarding which epsilon transition to add.
* @post if user provides valid state numbers i and j,
* epsilon[i][j] is set to true and the equivalent DFA is
* re-calculated
*/
protected void addEpsilonDialog()
{
int fromState, toState;
System.out.print("add epsilon transition FROM state number: ");
fromState = Util.readNum();
System.out.print("add epsilon transition TO state number: " );
toState = Util.readNum();
if(this.validState(fromState) && this.validState(toState))
{
epsilon[fromState][toState] = true;
D = this.convertToDFA(); // update the DFA
}
}
/**
* Queries user regarding which symbol-consuming transition to add.
* @post if user provides valid state numbers i and j, and valid symbol
* s, the transition array is changed accordingly and the equivalent
* DFA is re-calculated
*/
protected void addTransitionDialog()
// post: queries user for from-state (i), to-state (j), and alphabet
// symbol; adds transition (i,symbol) -> j if i and j are
// valid state numbers and symbol is in the alphabet;
// updates equiv dfa "D".
{
int fromState, toState, index;
String symbol;
System.out.print("add transition FROM state number: ");
fromState = Util.readNum();
System.out.print("add transition TO state number: " );
toState = Util.readNum();
System.out.print("add transition on SYMBOL: " );
symbol = Util.readString();
if(symbol.length()!=1)
return; // invalid symbol (not a single character)
index = alpha.toString().indexOf(symbol.charAt(0));
if(index<0)
return; // invalid symbol (not in alphabet)
if(this.validState(fromState) && this.validState(toState))
{
transition[fromState][toState][index] = true;
D = this.convertToDFA(); // update the DFA
}
}
/**
* Returns set of all states which are reachable from the given state on consuming
* the given input symbol.
* @param s the current state
* @param c the input symbol to be read
* @pre s is a valid state number
* @pre c is a symbol in the input alphabet
* @return ignoring the effects of epsilon transitions, this method returns an
* IntSet (set of integers) of all the states which are possible to reach from
* state s on consuming input symbol c
*/
public IntSet reachable(int s, char c)
{
IntSet R = new IntSet(); // a currently-empty set of integers (states)
int index = alpha.toString().indexOf(c); // position of char c in alpha
// stop & return empty set if either argument is invalid
if(index<0 || !this.validState(s)) return R;
// otherwise, iterate through transition array looking for reachable
// states
for(int j=0; j<numStates; j++)
if(transition[s][j][index])
R.add(j);
return R;
}
/**
* Returns set of all states which are reachable from at least one state
* in the given set on consuming the given input symbol.
* @param set current states
* @param c the input symbol to be read
* @return ignoring the effects of epsilon transitions, returns an IntSet
* of all the states which are reachable from at least one state in "set"
* on consuming input symbol c.
*/
public IntSet reachable(IntSet set, char c)
{
IntSet R = new IntSet();
for(int i=0; i<set.size(); i++)
{
// union all the sets "reachable(r,c)" where r varies over
// the states in "set" and c is the given alphabet symbol.
int r = set.elementAt(i);
R.union(reachable(r,c));
}
return R;
}
/**
* Returns the "E" array, where E[i] = set of all states reachable from
* state i in 0-or-more epsilon transitions.
* @return array of IntSets; E[i] is all states reachable from i in
* 0-or-more epsilon transitions
*/
public IntSet[] getE()
{
// Initialize temporary array E1.
// E1[i] will be all states reachable from i in ONE epsilon transition
IntSet[] E1 = new IntSet[numStates];
for(int i = 0; i<numStates; i++)
{
E1[i] = new IntSet();
for(int j=0; j<numStates; j++)
if(epsilon[i][j])
E1[i].add(j);
}
// E[i] will be all states reachable from i in 0 or more
// epsilon transitions
IntSet[] E = new IntSet[numStates];
for(int i=0; i<numStates; i++)
E[i] = new IntSet(i); // i is reachable from i in 0
// epsilon transitions
for(int k=0; k<numStates-1; k++) // in a graph with n nodes, no path
// needs length greater than n-1
for(int i=0; i<numStates; i++)
{
int length = E[i].size();
for(int j=0; j<length; j++) // for each state in E[i]...
{
int state = E[i].elementAt(j);
// add to E[i] those states which are one epsilon
// transition away from "state"
E[i].union(E1[state]);
}
}
return E;
}
/**
* Returns set of all states which are reachable from at least one
* state in the given set via 0-or-more epsilon transitions.
* @param set current states
* @return IntSet of all states reachable from "set" via 0-or-more
* epsilon transitions
*/
public IntSet getE(IntSet set)
{
IntSet R = new IntSet();
IntSet[] E = this.getE();
for(int i=0; i<set.size(); i++)
{
int r = set.elementAt(i);
R.union(E[r]);
}
return R;
}
/**
* Returns an array of DFA transitions for an equivalent DFA.
* @return an int array of size 2^numStates x alpha.size()
* holding all the transitions for an equivalent DFA
*/
public int[][] dfaSetTransitions()
{
int n = Util.twoPower(this.numStates); // # states in DFA
int[][] t = new int[n][alpha.size()]; // stores transitions
for(int i=0; i<n; i++) // for each state in the DFA...
{
// represent the "fromState" (i) as a set of states in the NFA
IntSet R = IntSet.setValue(i);
for(int j=0; j<alpha.size(); j++) // for each alphabet symbol
// find which state to transition to in the DFA
{
char c = alpha.charAt(j); // the alphabet symbol
// transition's destination can be represented as an
// IntSet (set of states in the NFA)
IntSet toState = new IntSet();
// add to "toState" all states in the NFA which are
// reachable from states in R, on reading jth alphabet
// symbol, with zero or more epsilon transitions AFTER
// the symbol-consuming transition
toState = reachable(R,c);
toState = getE(toState);
// convert the destination to an integer
// (a state in the DFA) and record in array "t"
t[i][j] = toState.intValue();
}
}
return t;
}
/**
* Returns an array of boolean values for "isFinal" array of an equivalent
* DFA.
* @return correct boolean values for "isFinal" array of an equivalent DFA
* whose set of states is equal to the power set of {0,1,2,...,numStates-1}
*/
public boolean[] dfaGetFinal()
// example: if a state [i,j,k] in the DFA contains at least one
// state which is final in the NFA, then [i,j,k] is final
// in the DFA, and the boolean value corresponding to
// [i,j,k].intValue is set to "true". If none of i,j,k
// are final in the NFA then [i,j,k] is not final in the
// DFA.
{
// calculate number of states in the DFA
int n = Util.twoPower(this.numStates);
// allocate a boolean array to hold return values
boolean[] f = new boolean[n];
for(int i=0; i<n; i++)
{ // as i ranges 0 to n-1, setValue(i) ranges over the
// set representations of the states in the DFA
IntSet set = IntSet.setValue(i);
// iterate thru the set of states; isFinal[i] becomes "true"
// in the DFA iff there exists a final state in "set"
for(int j=0; j<set.size(); j++)
if(isFinal[set.elementAt(j)])
{
f[i] = true;
break;
}
}
return f;
}
/**
* Returns a DFA which is equivalent to this NFA
* @return a DFA which is equivalent to this NFA; the DFA will
* not have inaccessible states and will recognize the same
* language as this NFA
*/
public DFA convertToDFA()
{
// calculate # states in the DFA
int n = Util.twoPower(numStates);
// store the state labels for the DFA in array L
String[] L = new String[n];
for(int i=0; i<n; i++)
L[i] = new String(IntSet.setValue(i).toString());
// store the DFA transitions in array t
int[][] t = dfaSetTransitions();
// make the DFA start from E([0])
IntSet R = new IntSet(0); // R = [0]
R = getE(R); // now R = E([0])
// R.toString() is the correct label for state R
String startState = new String(R.toString());
// find the final states for the dfa
boolean[] f = dfaGetFinal();
// create the DFA with the above specifications
DFA dfa = new DFA(n,L,startState,alpha.toString(),t,f);
dfa.prune(); // prune the dfa to eliminate inaccessible states
return dfa;
}
/**
* Replaces this NFA by its star closure.
* @post this NFA is replaced by the star-closure of this NFA: a new,
* final start state is created, with epsilon transition to old start;
* epsilon transitions are added from ALL final states to old start;
* the equivalent dfa "D" is re-calculated
*/
public void starClosure()
{
IntSet finalSet = this.getFinalSet(); // final states in this NFA
int fromState;
for(int i=0; i<finalSet.size(); i++)
{
// for each final state "fromState" ...
fromState = finalSet.elementAt(i);
// make an epsilon transition to old start
epsilon[fromState][0] = true;
}
// add a new start state, shifting all other states
// to make room (old start is now state #1)
this.addNewStart();
// add an epsilon transition from new start to old start
epsilon[0][1] = true;
// make new start final
isFinal[0] = true;
// recalculate the DFA
D = this.convertToDFA();
}
/**
* Adds a new start state, shifting all other states to make room.
* @post each state "i" becomes "i+1"; new state 0 is added;
* numStates is incremented; arrays "transition", "epsilon",
* and "isFinal" are updated to maintain all previous transitions
* and final states; does NOT update the dfa "D"; this must be
* done separately
*/
protected void addNewStart()
{
// update epsilon array
boolean[][] epsilonTemp = new boolean[numStates+1][numStates+1];
for(int i=1; i<=numStates; i++)
for(int j=1; j<=numStates; j++)
epsilonTemp[i][j] = epsilon[i-1][j-1];
epsilon = epsilonTemp;
// update transition array
boolean[][][] transTemp =
new boolean[numStates+1][numStates+1][alpha.size()];
for(int i=1; i<=numStates; i++)
for(int j=1; j<=numStates; j++)
for(int k=0; k<alpha.size(); k++)
transTemp[i][j][k] = transition[i-1][j-1][k];
transition = transTemp;
// update isFinal array
boolean[] finalTemp = new boolean[numStates+1];
for(int i=1; i<=numStates; i++)
finalTemp[i] = isFinal[i-1];
isFinal = finalTemp;
// increment numStates
numStates++;
}
/**
* Tests whether this NFA accepts a given input string.
* @param inString the String to be tested
* @return true iff this NFA accepts inString
*/
public boolean accepts(String inString)
{
return D.accepts(inString);
}
/**
* Allows the user to repeatedly test strings on this NFA.
* @post Each input string is echoed back to the console with a report
* of the string's length and whether or not it is accepted
*/
protected void testingDialog()
{
D.testingHandler();
}
/**
* Pretty-prints this NFA's specifications.
* @post prints report on numStates, Alphabet, start state,
* final states, and transitions
*/
public void printNFA()
{
// report numStates
System.out.println("numStates = " + numStates);
// report alphabet
System.out.print("alphabet = " + alpha.toPrettyString()+"\n");
// report start state
System.out.println("The start state is: 0");
printFinal(); // print the final states of the NFA
printTransitions(); // print all transitions
}
/**
* Prints list of final states in this NFA.
*/
public void printFinal()
{
IntSet finalSet = this.getFinalSet();
System.out.println("The final states are: " + finalSet);
}
/**
* Prints all the transitions in form "(i,x) -> j".
*
*/
public void printTransitions()
{
System.out.println("Transition function:");
// first the "regular" transitions
for(int i=0; i<numStates; i++)
for(int j=0; j<numStates; j++)
for(int k=0; k<alpha.size(); k++)
if(transition[i][j][k])
System.out.println("(" + i + "," +
alpha.charAt(k) + ") -> " + j);
// then the "epsilon" transitions
for(int i=0; i<numStates; i++)
for(int j=0; j<numStates; j++)
if(epsilon[i][j])
System.out.println("(" + i + "," + "epsilon" +
") -> " + j);
System.out.println();
}
/**
* Prints the language accepted by this NFA up through a given maximum
* length.
* @param n maximum string length to be printed
* @pre n >= 0
* @post prints the language accepted by this NFA, in lexicographic
* order, up through strings of length n
*/
public void printLanguage(int n)
{
D.printLanguage(n);
}
/**
* Makes "this" into an NFA corresponding to Sipser, Figure 1.27.
* @post all data fields are initialized to represent the
* desired NFA
*/
protected void constructN1()
{
numStates = 4;
alpha = new Alphabet("01");
transition = new boolean[numStates][numStates][alpha.size()];
transition[0][0][0] = true; // (q1,0)->q1
transition[0][0][1] = true; // (q1,1)->q1
transition[0][1][1] = true; // (q1,1)->q2
transition[1][2][0] = true; // (q2,0)->q3
transition[2][3][1] = true; // (q3,1)->q4
transition[3][3][0] = true; // (q3,0)->q3
transition[3][3][1] = true; // (q3,1)->q3
epsilon = new boolean[numStates][numStates];
epsilon[1][2] = true; // (q2,epsilon)->q3
isFinal = new boolean[numStates];
isFinal[3] = true;
D = this.convertToDFA();
}
/**
* Makes "this" into an NFA corresponding to Sipser, Figure 1.31.
* @post all data fields are initialized to represent the
* desired NFA
*/
protected void constructN2()
{
numStates = 4;
alpha = new Alphabet("01");
transition = new boolean[numStates][numStates][alpha.size()];
transition[0][0][0] = true; // (q1,0)->q1
transition[0][0][1] = true; // (q1,1)->q1
transition[0][1][1] = true; // (q1,1)->q2
transition[1][2][0] = true; // (q2,0)->q3
transition[1][2][1] = true; // (q2,1)->q3
transition[2][3][0] = true; // (q3,0)->q4
transition[2][3][1] = true; // (q3,1)->q4
epsilon = new boolean[numStates][numStates];
isFinal = new boolean[numStates];
isFinal[3] = true;
D = this.convertToDFA();
}
/**
* Makes "this" into an NFA corresponding to Sipser, Figure 1.34.
* @post all data fields are initialized to represent the
* desired NFA
*/
protected void constructN3()
{
numStates = 6;
alpha = new Alphabet("0");
transition = new boolean[numStates][numStates][alpha.size()];
transition[1][2][0] = true; // (q1,0)->q2
transition[2][1][0] = true; // (q2,0)->q1
transition[3][4][0] = true; // (q3,0)->q4
transition[4][5][0] = true; // (q4,0)->q5
transition[5][3][0] = true; // (q5,0)->q3
epsilon = new boolean[numStates][numStates];
epsilon[0][1] = true; // (q0,epsilon)->q1
epsilon[0][3] = true; // (q0,epsilon)->q3
isFinal = new boolean[numStates];
isFinal[1] = true;
isFinal[3] = true;
D = this.convertToDFA();
}
/**
* Makes "this" into an NFA corresponding to Sipser, Figure 1.36.
* @post all data fields are initialized to represent the
* desired NFA
*/
protected void constructN4()
{
numStates = 3;
alpha = new Alphabet("ab");
transition = new boolean[numStates][numStates][alpha.size()];
transition[0][1][1] = true; // (q1,b)->q2
transition[1][1][0] = true; // (q2,a)->q2
transition[1][2][0] = true; // (q2,a)->q3
transition[1][2][1] = true; // (q2,b)->q3
transition[2][0][0] = true; // (q3,a)->q1
epsilon = new boolean[numStates][numStates];
epsilon[0][2] = true; // (q1,epsilon)->q3
isFinal = new boolean[numStates];
isFinal[0] = true;
D = this.convertToDFA();
}
// ** TEST METHOD **
public static void main(String[] args) {
new NFA();
}
}