package finiteAutomata;
/**
* Nondeterministic Finite Automaton.
*
*
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).
*
*
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".
*
*
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.
*
*
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=0 && i> 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> 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 j".
*
*/
public void printTransitions()
{
System.out.println("Transition function:");
// first the "regular" transitions
for(int i=0; i " + j);
// then the "epsilon" transitions
for(int i=0; i " + 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();
}
}