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();	
	}
}