package finiteAutomata;

import java.util.Vector;

/**
 * Chomsky Normal Form grammar. Every context-free grammar can be represented 
 * by an equivalent CNF grammar.  
 * 
 * <BR><BR>A CNF grammar has a non-empty set of variables,
 * a non-empty set of terminal symbols (disjoint from the set of variables),
 * and a set of production rules for transforming the variables.  One of the
 * variables is singled out as the "start" variable.  
 *
 * <BR><BR>Data Fields:  The terminal symbols of a CNF object are stored as 
 * an Alphabet, "alpha".  The variables are denoted v0, v1, v2, etc., where 
 * v0 is always the start variable.  "numVars" records the number of variables 
 * in the grammar.
 *
 * <BR><BR>The grammar rules are stored in a two-dimensional array (numVars x 2) 
 * of Vectors of CNFRule objects.  If vn is one of the variables, all the 
 * type 0 rules for transforming vn (form "vn -> vi vj" are stored in the 
 * Vector "rule[n][0]", and all the type 1 rules for transforming vn 
 * (form "vn -> terminal") are stored in the Vector "rule[n][1]". 
 *
 * <BR><BR>If the rule "v0 -> epsilon" is included in the grammar, the boolean 
 * variable "startToEpsilon" is set to true (this is the only rule not 
 * stored in the rule array).
 * 
 * @author Barbara Wahl
 * @version Fall 2007
*/
public class CNF {
	// ** DATA FIELDS **
	/**
	 * terminal symbols
	 */
	protected Alphabet alpha;    
	
	/**
	 * number of variables
	 */
	protected int numVars;   
	
	/**
	 * true if "v0 -> epsilon" is a rule
	 */
	protected boolean startToEpsilon;
	
	/**
	 * array of Vectors of CNFRule objects; rule[i][j] contains 
	 * all the type j rules which transform vi
	 */
	protected Vector[][] rule;        
	
	// ** CONSTRUCTORS **
	/**
	 * 0-parameter constructor, prompts the user for CNF information.
	 * @post constructs a CNF grammar with all data fields set according 
	 * to user input
	 */
	public CNF()
	{
		int choice;
		
		// predefined = true if user wants to use a predefined CNF object
		boolean predefined = queryPredefined();
		if(predefined)
			predefinedDialog();
		else
		{   // "alpha" & "numVars" for user-defined CNF
			numVars = queryNumVars();
			alpha = new Alphabet(queryAlphabet());
			startToEpsilon = false;	
			// allocate 2-dim'l array to hold references to Vectors
			rule = new Vector[numVars][2];  			                               
			for(int i=0; i<numVars; i++)
				for(int j=0; j<2; j++)
					// create the empty rule Vectors
					rule[i][j] = new Vector(); 
		}
		
		// show current state of this CNF grammar
		System.out.println("Current Grammar:");
		this.printCNF();
		
		// repeatedly display menu, allowing user to add rules, etc.		
		while(true)
		{
			choice = constructorMenu(); // get user action choice
			if(choice == 6)
				break; // user is done -- exit while loop
			else menuHandler(choice);
		} 
		System.out.println("Bye-bye!");		
	}
	
	/**
	 * 4-parameter constructor.
	 * @param a String representation of the desired alphabet with 
	 * characters listed in the desired lexicographic order
	 * @param n int number of desired variables
	 * @param b true iff "v0 -> epsilon" is to be a rule
	 * @param r 2-dimensional array of Vectors of CNFRule objects 
	 * @pre a is a non-empty string with no repeated characters
	 * @pre n > 0
	 * @pre r is size n x 2, and for each 0 <= i < n, r[i][j] is a
	 * non-null Vector (possibly empty) of CNFRule objects of type j
	 * which transform the variable vi (j = 0, 1)
	 * @post constructs a CNF grammar with Alphabet a, n variables,
	 * with rules given by the array r (and v0 -> epsilon iff b == true);
	 * the data field "rule" simply references r (r is not copied)
	 */
	public CNF(String a, int n, boolean b, Vector[][] r)
	{
		Assert.pre(n > 0, "n is positive");
		alpha = new Alphabet(a);
		numVars = n;
		startToEpsilon = b;
		rule = new Vector[n][2];
		for(int i=0; i<n; i++)
		{
			rule[i][0] = r[i][0];
			rule[i][1] = r[i][1];
		}
	}
	
	// ** PUBLIC METHODS **
	
	/**
	 * Adds rule "vn -> t" to the rule set.
	 * @param n integer specifying LHS variable
	 * @param t char specifying terminal symbol for RHS
	 * @pre n is a valid variable number for this CNF
	 * @pre t is a valid terminal symbol for this CNF
	 * @post if preconditions are met, and if the rule does not currently 
	 * exist, the rule "vn -> t" is added to this CNF's rule set;
	 * otherwise, warning message is printed
	 */
	public void addTypeOne(int n, char t)
	{
		if(!this.isValidVariable(n) || !alpha.contains(t))
		{
			System.out.println("Invalid rule not added; can't have ");
			System.out.print(new CNFRule(n,t));
			return;
		}
		
        // check if this rule already exists
		CNFRule newRule = new CNFRule(n,t);
		if(rule[n][1].contains(newRule))
			System.out.println("Rule " + newRule + 
					" was not added (it already exists).");
		
        // proceed to add this rule
		else
		{
			rule[n][1].add(newRule);
			System.out.println("The rule " + newRule + " +" +
					"has been added.");
		}	
	}
	
	
	/**
	 * Adds rule "vn -> vi vj" to the rule set.
	 * @param n integer specifying LHS variable
	 * @param i integer specifying first RHS variable
	 * @param j integer specifying second RHS variable
	 * @pre n, i, and j are valid variable numbers for this CNF
	 * @post if preconditions are met, if i>0 and j>0, and if
	 * the rule does not currently exist, rule "vn -> vi vj" 
	 * is added to this CNF's rule set; otherwise, warning 
	 * message is printed
	 */
	public void addTypeZero(int n, int i, int j)
	{
		if(!this.isValidVariable(n) || !this.isValidVariable(i) || 
				!this.isValidVariable(j) ||	i == 0 || j == 0)
			{
				System.out.println("Invalid rule not added; " +
						"can't have ");
				System.out.print(new CNFRule(n,i,j));
				return;
			}
		
		// check if this rule already exists
		CNFRule newRule = new CNFRule(n,i,j);
		if(rule[n][0].contains(newRule))
			System.out.println("Rule " + newRule + 
					" was not added (it already exists).");
		
		// proceed to add this rule
		else
		{
			rule[n][0].add(newRule);
			System.out.println("The rule " + newRule + " +" +
					"has been added.");
		}
	}
	
	
	/**
	 * Returns all non-empty terminal strings derivable in a given number 
	 * of steps.
	 * @param maxSteps int upper bound on derivation length
	 * @return Vector containing all NON-EMPTY terminal strings derivable 
	 * in maxSteps or fewer steps from start; strings with multiple 
	 * derivations WILL appear multiple times
	 */
	public Vector getLanguage(int maxSteps)
	{
		Vector q = new Vector();         // working space (use as queue)
		q.add(new StringVarTerm(alpha)); // enqueue the start string, "v0"		
		Vector result = new Vector();    // store strings for return		
		StringVarTerm current = (StringVarTerm) q.elementAt(0);
		StringVarTerm newString;
		CNFRule r;
		int leftMostIndex; // position of left-most variable in current
		int lmv;           // left-most variable in current	
		int head = 0;      // index for top-of-queue (for lazy deletion)
		
		// PLAN: current = q.dequeue; while current.numSteps isn't too 
		// large, either store current (if it has no vars) or use current 
		// to generate more strings (enqueue the new strings at tail of 
		// q & repeat)
		while(current.numSteps() <= maxSteps)
		{
			head++; // effectively, q.dequeue
			if(current.vars() == 0) // current is all terminals -- store it!
				result.add(current);		
			// Otherwise, apply each applicable rule to "current" & 
			// enequeue results (FIRST check current.numSteps < maxSteps)
			else if(current.numSteps() < maxSteps)
			{
				leftMostIndex = current.leftMostVarIndex();
				lmv = current.decodeVar(leftMostIndex); 
				
				// code to prevent useless application of type 0 rules
				int jStart = 0;
				if(current.numSteps() + current.vars() >= maxSteps)
					jStart = 1;
				
				// for each rule which applies to left-most-variable "lmv"...
				for(int j = jStart; j<2; j++) // j = rule type
					for(int i=0; i<this.rule[lmv][j].size(); i++)
					{
	    				// r is the ith applicable rule of its type
						r = (CNFRule)(this.rule[lmv][j]).elementAt(i); 
						newString = current.applyRule(r); 
						q.add(newString); // enqueue result
					}
			}
			// stop if queue is empty
			if(head >= q.size()) break;
			// dequeue to current and repeat until maxSteps exceeded
			current = (StringVarTerm)q.elementAt(head); 			
		}
		return result;
	}
	
	/**
	 * Returns all non-empty terminal strings derivable in a given number 
	 * of steps, without repetitions.
	 * @param maxSteps int upper bound on derivation length
	 * @return Vector containing all NON-EMPTY terminal strings derivable 
	 * in maxSteps or fewer steps from start; strings with multiple 
	 * derivations will NOT appear multiple times
	 */
	public Vector getLanguageUnambiguous(int maxSteps)
	{
		Vector q = new Vector();         // working space (use as queue)
		q.add(new StringVarTerm(alpha)); // enqueue the start string, "v0"		
		Vector result = new Vector();    // store terminal strings for return		
		StringVarTerm current = (StringVarTerm) q.elementAt(0);
		StringVarTerm newString;
		CNFRule r;
		int leftMostIndex; // position of left-most variable in current
		int lmv;           // left-most variable in current	
		int head = 0;      // index for top-of-queue (for lazy deletion)
		Hashtable used = new Hashtable(9973); // creates a hashtable with 
		                                      // tableSize = 9973 (lg prime)
		String key; // will use String objects as keys
		// PLAN: current = q.dequeue; while current.numSteps is not too 
		// large, either store current (if it has no vars) or use current 
		// to generate more strings (enqueue the new strings at tail of 
		// q & repeat). We avoid repetitions as follows.  
		// First, each time an element is added to "q", it is also put into
		// the hashtable "used".  Second, if an element "newString" 
		// representsthe same string of variables and terminals (maybe with 
		// a different derivation) as any element already in hashtable 
		// "used", then "newString" will not be added to "q".
		while(current.numSteps() <= maxSteps)
		{
			head++;  // effectively, q.dequeue
			if(current.vars() == 0) // current is all terminals; store
				result.add(current);
									
			// Otherwise, apply each applicable rule to "current" & 
			// enqueue results (check current.numSteps < maxSteps)
			else if(current.numSteps() < maxSteps)
			{
				leftMostIndex = current.leftMostVarIndex();
				lmv = current.decodeVar(leftMostIndex); 
				
				// prevent useless application of type 0 rules
				int jStart = 0;
				if(current.numSteps() + current.vars() >= maxSteps)
					jStart = 1;
				
				// for each rule applicable to "lmv"...
				for(int j = jStart; j<2; j++) // j = rule type
					for(int i=0; i<this.rule[lmv][j].size(); i++)
					{
	    				// r is the ith applicable rule of type j
						r = (CNFRule)(this.rule[lmv][j]).elementAt(i); 
						newString = current.applyRule(r); 
						key = newString.toPrettyString();
						if(!used.contains(key))
						{
							q.add(newString); // enqueue 
							used.insert(key,null); // add to hashtable
						}
					}
			}
			if(head >= q.size()) 
				break; // stop if q is (virtually) empty
					   // or, dequeue to current and repeat
			current = (StringVarTerm)q.elementAt(head); 	 			
		}
		System.out.println("Hashtable max load factor = " + 
				used.loadFactor());
		return result;
	}
		
	/**
	 * Tests whether a given integer is a valid variable number.
	 * number for this CNF
	 * @param i int variable number to be tested
	 * @return true iff i >= 0 and i < number of variables in this CNF
	 */	
	public boolean isValidVariable(int i)
	{
		return (i >= 0 && i < numVars);
	}
	
	
	/**
	 * Reports number of variables, alphabet of terminal symbols, and 
	 * rule set.
	 */
	public void printCNF()
	{
		System.out.println("numVars = " + numVars);
		System.out.println("alphabet of terminals = " + 
				alpha.toPrettyString());
		System.out.println("grammar rules:");
		printRules();
	}
	
	/**
	 * Pretty-prints the rule set.
	 */
	public void printRules()
	{
		CNFRule theRule;
		
		if(startToEpsilon)
			System.out.println("v0 -> epsilon");
		
		for(int n = 0; n < numVars; n++) // for each LHS variable n
			for(int t = 0; t < 2; t++) // for both rule types t
				// iterate thru rule[n][t]
				for(int i = 0; i < rule[n][t].size(); i++) 
				{
					theRule = (CNFRule)rule[n][t].elementAt(i);
					System.out.println(theRule);
				}
	}	
	
	/**
	 * Removes rule "vn -> t" from the rule set.
	 * @param n integer specifying LHS variable
	 * @param t char specifying terminal symbol for RHS
	 * @post if rule is present, removes rule "vn -> t" from
	 * this CNF's rule set and informs user of deletion
	 */ 
	public void removeTypeOne(int n, char t)
	{
		if(this.isValidVariable(n) && alpha.contains(t))
			rule[n][1].remove(new CNFRule(n,t));
		System.out.println("The rule " + new CNFRule(n,t) + 
				" has been removed.");
	}
	

	/**
	 * Removes rule "vn -> vi vj" from the rule set.
	 * @param n integer specifying LHS variable
	 * @param i integer specifying first RHS variable
	 * @param j integer specifying second RHS variable
	 * @pre n, i, and j are valid variable numbers for this CNF
	 * @post if rule is present, removes rule "vn -> vi vj" from
	 * this CNF's rule set and informs user of deletion
	 */
	public void removeTypeZero(int n, int i, int j)	
	{
		if(this.isValidVariable(n) && this.isValidVariable(i) && 
				this.isValidVariable(j) && i > 0 && j > 0)
			rule[n][0].remove(new CNFRule(n,i,j));
		System.out.println("The rule " + new CNFRule(n,i,j) + 
				" has been removed.");
	}
	
	
	/**
	 * Tests whether a given String is a terminal string which can be
	 * generated by this CNF.
	 * @param s String to be tested 
	 * @return the StringVarTerm object which shows how s is generated,
	 * or "null" if s is not in the language of this CNF grammar
	 */
	public StringVarTerm testString(String s)
	{
		int n = s.length();    
		if(n==0 || !alpha.indexArray(s,new int[n]))
				return null;  // give up if s not valid argument				
				
		// generate all strings up through length n using this CNF grammar
		// Theorem:  if s is a string of length n>0 in the language of
		// of a CNF grammar, then every derivation of s has length 2*n-1.
		Vector language = this.getLanguageUnambiguous(2*n-1);
		
		// look for s among the StringVarTerm objects in lang
		StringVarTerm current;
		for(int i=0; i<language.size(); i++)
		{
			current = (StringVarTerm)language.elementAt(i);
            // if "current" and "s" represent the terminal string
			if(current.equalTermString(s)) 
				return current; // success!
		}
		return null; // s not found in language
	}
	
	// ** MENU AND QUERY METHODS **	
	/**
	 * Asks user if they want to use a pre-defined CNF.
	 * @return true iff user's response begins with 'Y' or 'y'
	 */
	protected boolean queryPredefined()
	{
		System.out.print("Do you want to use a pre-defined CNF? " +
				"Enter Y or N: ");
		return Util.answerIsYes();
	}
	
	/**
	 * Queries user regarding which pre-defined CNF they will use.
	 * @post initializes this CNF to have the same data fields as the 
	 * pre-defined grammar chosen by the user
	 */
	protected void predefinedDialog()
	{
		int num;
		while(true)
		{
			System.out.println("Choose a pre-defined CNF grammar: ");
			System.out.println("  1 = equiv to Sipser G1, p.100");
			System.out.println("  2 = equiv to Sipser G3, p.103");
			System.out.println("  3 = equiv to Sipser G6, p.108");
			System.out.println("  4 = CNF grammar for 0*10*");
			System.out.println("  5 = CNF grammar for palindromes on" +
					" {0,1}");
			num = Util.readNum();
			if(0 < num && num < 6) 
				break;
		}
		switch(num){
		case 1: 
			constructC1();
			break;
		case 2: 
			constructC2();
			break;
		case 3: 
			constructC3();
			break;
		case 4: 
			constructC4();
			break;
		case 5: 
			constructC5();
			break;
		}
	}
	
	/**
	 * Queries user for alphabet of terminal symbols.
	 * @return String of terminal symbols as specified by user
	 */
	protected String queryAlphabet()
	{
		System.out.print(">> Enter a string with no spaces or " +
			"repeated characters (terminal symbols): ");
		return Util.readString();
	}
	
	/**
	 * Prints constructor menu header and queries user regarding number 
	 * of variables.
	 * @return positive integer number of variables as specified by user
	 */
	protected int queryNumVars()
	{
		int num = 0; // temp storage for integer input
		System.out.println("****** CNF CONSTRUCTOR MENU ******");
		
		// ask user how many variables; only accept num > 0
		while(num < 1)
		{
			System.out.print(">> Enter a positive integer " +
					"(number of variables): ");
			num = Util.readNum();
		}
		return num;
	}
	
	/**
	 * Asks user if they want to have strings with ambiguous derivations
	 * be repeated.
	 * @return true iff user response begins with 'Y' or 'y'
	 */
	protected boolean queryAmbiguous()
	{
		System.out.print("Repeat strings with ambiguous derivations? " +
				"Enter Y or N: ");
		return Util.answerIsYes();
	}
	
	/**
	 * Repeatedly displays constructor menu options until user makes 
	 * a valid choice.
	 * @return int choice number from 1 to 6
	 */
	protected int constructorMenu()
	{
		int choice = -1;
		
		while(choice < 1 || choice > 6)
		{		
			System.out.println("\nChoose an action: ");
			System.out.println("  1 = add/remove a rule");
			System.out.println("  2 = print this CNF grammar");
			System.out.println("  3 = print the language of this" +
					" CNF grammar");
			System.out.println("  4 = test a non-empty string");
			System.out.println("  5 = test the epsilon string");
			System.out.println("  6 = DONE with this CNF grammar");
			
			choice = Util.readNum();
		}
		return choice;
	}
	
	/**
	 * Takes the appropriate action based on constructorMenu options.
	 * @param choice integer code for user's desired action
	 * @pre 1 <= choice <= 5
	 */
	protected void menuHandler(int choice)
	{
		Assert.pre(1 <= choice && choice <= 5,
				"1 <= choice <= 5");
		switch (choice)
		{
		case 5: // test epsilon string
			if(this.startToEpsilon)
				System.out.println("epsilon is accepted");
			else System.out.println("epsilon is rejected");
			break;
		case 4: // test a non-epsilon string
			testStringDialog();
			break;
		case 3: // print language
			printLanguageDialog();
			break;
		case 2: // print CNF
			printCNF();
			break;
		case 1: // add/remove a rule
			ruleChangeDialog();
		} 
	}
	
	/**
	 * Asks user which type of rule change they want to make
	 * and carries out that request.
	 * @post rule array is altered to reflect addition/deletion 
	 * of a rule, or value of startToEpsilon is possibly changed
	 */
	protected void ruleChangeDialog()
	{
		int n = -1;
		while(n<0 || n>5)
		{
			System.out.println("Choose an option: ");
			System.out.println("  0 = add a rule, form 0,  " +
					"vn -> vi vj");
			System.out.println("  1 = add a rule, form 1,  " +
					"vn -> terminal");
			System.out.println("  2 = add a rule, form 2,  " +
					"start -> epsilon");
			System.out.println("  3 = remove a rule, form 0, " +
					"vn -> vi vj");
			System.out.println("  4 = remove a rule, form 1, " +
					"vn -> terminal");
			System.out.println("  5 = remove a rule, form 2, " +
					"start -> epsilon");
			n = Util.readNum();
		}
		switch(n)
		{
			case 5: // remove rule type 2, start -> epsilon
				startToEpsilon = false;
				System.out.println("The rule v0 -> epsilon " +
						"has been removed.");
				break;
			case 4: // remove rule type 1, vn -> terminal
				removeTypeOneDialog(); 
				break;
			case 3: // remove rule type 0, vn -> vi vj
				removeTypeZeroDialog();
				break;
			case 2: // add rule type 2, start -> epsilon
				startToEpsilon = true;
				System.out.println("The rule v0 -> epsilon " +
						"has been added.");
				break;
			case 1: // add rule type 1, vn -> terminal
				addTypeOneDialog();
				break;		
			case 0: // add rule type 0, vn -> vi vj
				addTypeZeroDialog();
		}
	}
	
	/**
	 * Queries user for n, i, and j in the rule "vn -> vi vj" and adds 
	 * the correpsonding rule.
	 * @post rule array is updated
	 */
	protected void addTypeZeroDialog()
	{
		int n=-1, i=-1, j=-1;
		System.out.println("Adding rule of type 0, form vn -> vi vj.");
		while(n<0 || n>=numVars)
		{
			System.out.print("Enter value for n, the LHS variable:" +
					" n = ");
			n = Util.readNum();
		}
		while(i<1 || i>=numVars)
		{
			System.out.print("Enter value for i, the first " +
					"RHS variable: i = ");
			i = Util.readNum();
		}
		while(j<1 || j>=numVars)
		{
			System.out.print("Enter value for j, the second " +
					"RHS variable: j = ");
			j = Util.readNum();
		}
		this.addTypeZero(n,i,j);		
	}
	
	/**
	 * Queries user for n and t in the rule "vn -> t" and adds 
	 * the correpsonding rule.
	 * @post rule array is updated
	 */
	protected void addTypeOneDialog()
	{
		int n = -1;
		char t = ' ';
		System.out.println("Adding rule of type 1, form vn -> t.");
		while(n<0 || n>=numVars)
		{
			System.out.print("Enter value for n, the LHS variable: " +
					"n = ");
			n = Util.readNum();
		}
		while(!alpha.contains(t))
		{
			System.out.print("Enter a terminal symbol for RHS: t = ");
			// assume terminal = first char from the input string
			t = Util.readString().charAt(0); 
		}
		this.addTypeOne(n,t);		
	}

	/**
	 * Queries user for n, i, and j, and removes rule "vn -> vi vj".
	 * @post rule array is updated
	 */
	protected void removeTypeZeroDialog()
	{
		int n=-1, i=-1, j=-1;
		System.out.println("Removing rule of type 0, form vn -> vi vj.");
		while(n<0 || n>=numVars)
		{
			System.out.print("Enter value for n, the LHS " +
					"variable: n = ");
			n = Util.readNum();
		}
		while(i<1 || i>=numVars)
		{
			System.out.print("Enter value for i, the first RHS " +
					"variable: i = ");
			i = Util.readNum();
		}
		while(j<1 || j>=numVars)
		{
			System.out.print("Enter value for j, the second RHS " +
					"variable: j = ");
			j = Util.readNum();
		}
		this.removeTypeZero(n,i,j);		
	}

	/**
	 * Queries user for n and t, and removes rule "vn -> t".
	 * @post rule array is updated
	 */
	protected void removeTypeOneDialog()
	{
		int n = -1;
		char t = ' ';
		System.out.println("Removing rule of type 1, form vn -> t.");
		while(n<0 || n>=numVars)
		{
			System.out.print("Enter value for n, the LHS variable: " +
					"n = ");
			n = Util.readNum();
		}
		while(!alpha.contains(t))
		{
			System.out.print("Enter a terminal symbol for RHS: t = ");
			// assume terminal = first char from the input string
			t = Util.readString().charAt(0); 
		}
		this.removeTypeOne(n,t);		
	}
	
	/**
	 * Queries user for max string length and prints this CNF's language.
	 * @post all terminal strings generated by this CNF, up to the 
	 * user-specified max length, are printed; according to user 
	 * input, derivations may also be printed and strings with ambiguous
	 * derivations may appear multiple times
	 */
	protected void printLanguageDialog()
	{
		int n = -1;
		while(n<=0)
		{
			System.out.print("Enter a positive value for n " +
					"(max derivation length): ");
			n = Util.readNum();
		}
		boolean printDeriv = false;
		System.out.print("Enter YES if you want to also print " +
				"the derivations: ");
		String inString = Util.readString();
		if(inString.charAt(0) == 'y' || inString.charAt(0) == 'Y')
			printDeriv = true;
		Vector lang;
		
		// ask whether to repeat strings with ambiguous derivations
		boolean ambiguous = queryAmbiguous(); 		                                         
		if(ambiguous)
			lang = getLanguage(n);
		else lang = getLanguageUnambiguous(n);
		this.printLanguage(lang, printDeriv);		
	}
	
	/**
	 * Determines whether a user-specified String is generated by this grammar.
	 * @post reports the result of the test and, if accepted, a derivation
	 * of the string
	 */
	protected void testStringDialog()
	{
		String inString;
		System.out.print("Enter a string to test: ");
		inString = Util.readString();
		StringVarTerm result = testString(inString);
		if(result!=null)
		{
			System.out.print(inString + " is accepted!");
			System.out.print("\nDerivation: ");
			result.printDerivation();
		}
		else System.out.println(inString + " is rejected");		
	}
	
	// ** OTHER METHODS **
	/**
	 * Prints the strings in the given Vector, preceded by "epsilon" if
	 * epsilon is generated by this CNF.
	 * @param v Vector representing the non-epsilon terminal strings 
	 * generated by this CNF (up to some maximum derivation length)
	 * @param printDeriv determines whether the derivation of each 
	 * string is also printed
	 * @pre v is a non-null Vector of non-null StringVarTerm objects
	 * @post if v is empty and if epsilon is not generated, reports that
	 * "the language is empty"
	 */
	protected void printLanguage(Vector v, boolean printDeriv)
	{
		StringVarTerm s;
		
		if(v.isEmpty() && !startToEpsilon) // empty language
		{
			System.out.println("Language is empty!");
			return;
		}
		
		System.out.println("\nLanguage strings:");
		
		if(this.startToEpsilon)
		{
			System.out.print("epsilon");
			if(printDeriv)
				System.out.print(": v0 -> epsilon");
			System.out.println();
		}
		
		// iterate thru v, printing each string
		for(int i=0; i<v.size(); i++)
		{
			s = ((StringVarTerm)v.elementAt(i));
			System.out.print(s.toPrettyString());
			if(printDeriv)
			{
				System.out.print(": ");
				s.printDerivation();
			}
			else System.out.println();
		}
	}	
	
	// ** METHODS TO CREATE PRE-DEFINED GRAMMARS **
	/**
	 * Initializes this to be a CNF grammar equivalent to Sipser's G1 (p.100).
	 * @post data fields of this CNF grammar are set accordingly
	 */
	protected void constructC1()
	{
		alpha = new Alphabet("01#"); // alphabet symbols
		numVars = 5;
		startToEpsilon = false; // start -> epsilon not a rule
		
		rule = new Vector[numVars][2]; // array of Vectors for rules
		
		// Create the rule Vectors
		for(int i=0; i<numVars; i++)
			for(int j=0; j<2; j++)
				rule[i][j] = new Vector();

		// create & store the rules for this grammar
		rule[0][0].add(new CNFRule(0,3,4)); // v0 -> v3 v4
		rule[0][1].add(new CNFRule(0,'#'));  // v0 -> #
		rule[1][0].add(new CNFRule(1,3,4));  // v1 -> v3 v4
		rule[1][1].add(new CNFRule(1,'#'));  // v1 -> #
		rule[2][1].add(new CNFRule(2,'1'));  // v2 -> 1
		rule[3][1].add(new CNFRule(3,'0'));  // v3 -> 0
		rule[4][0].add(new CNFRule(4,1,2));  // v4 -> v1 v2		

	}
	
	/**
	 * Initializes this to be a CNF grammar equivalent to Sipser's G3 (p.103).
	 * @post data fields of this CNF grammar are set accordingly
	 */
	 protected void constructC2()
	{
		alpha = new Alphabet("ab"); // alphabet symbols
		numVars = 5; // numVars
		startToEpsilon = true; // start -> epsilon is a rule
		
		rule =  new Vector[numVars][2]; // array of Vectors for rules
		// Create the rule Vectors
		for(int i=0; i<numVars; i++)
			for(int j=0; j<2; j++)
				rule[i][j] = new Vector();

		// create & store the rules for this grammar
		rule[0][0].add(new CNFRule(0,3,2)); // v0 -> v3 v2
		rule[0][0].add(new CNFRule(0,1,1)); // v0 -> v1 v1
		rule[0][0].add(new CNFRule(0,3,4)); // v0 -> v3 v4
		rule[1][0].add(new CNFRule(1,3,2)); // v1 -> v3 v2
		rule[1][0].add(new CNFRule(1,1,1)); // v1 -> v1 v1
		rule[1][0].add(new CNFRule(1,3,4)); // v1 -> v3 v4
		rule[2][0].add(new CNFRule(2,1,4)); // v2 -> v1 v4
		rule[3][1].add(new CNFRule(3,'a')); // v3 -> a
		rule[4][1].add(new CNFRule(4,'b')); // v4 -> b	
	}
	 
	/**
	* Initializes this to be a CNF grammar equivalent to Sipser's G6 (p.108).
	* @post data fields of this CNF grammar are set accordingly
	*/
	protected void constructC3()
	{
		alpha = new Alphabet("ab"); // alphabet symbols
		numVars = 6; // numVars
		startToEpsilon = false; // start -> epsilon not a rule
		
		rule = new Vector[numVars][2]; // array of Vectors for rules
		// Create the rule Vectors
		for(int i=0; i<numVars; i++)
			for(int j=0; j<2; j++)
				rule[i][j] = new Vector();

		// create & store the rules for this grammar
		rule[0][1].add(new CNFRule(0,'a')); // v0 -> a				
		rule[0][0].add(new CNFRule(0,1,2)); // v0 -> v1 v2
		rule[0][0].add(new CNFRule(0,4,5)); // v0 -> v4 v5
		rule[0][0].add(new CNFRule(0,2,1)); // v0 -> v2 v1
		rule[0][0].add(new CNFRule(0,2,3)); // v0 -> v2 v3		
		rule[1][1].add(new CNFRule(1,'a')); // v1 -> a		
		rule[1][0].add(new CNFRule(1,1,2)); // v1 -> v1 v2
		rule[1][0].add(new CNFRule(1,4,5)); // v1 -> v4 v5			
		rule[1][0].add(new CNFRule(1,2,1)); // v1 -> v2 v1
		rule[1][0].add(new CNFRule(1,2,3)); // v1 -> v2 v3
		rule[2][1].add(new CNFRule(2,'a')); // v2 -> a
		rule[2][1].add(new CNFRule(2,'b')); // v2 -> b		
		rule[2][0].add(new CNFRule(2,1,2)); // v2 -> v1 v2
		rule[2][0].add(new CNFRule(2,4,5)); // v2 -> v4 v5				
		rule[2][0].add(new CNFRule(2,2,1)); // v2 -> v2 v1
		rule[2][0].add(new CNFRule(2,2,3)); // v2 -> v2 v3
		rule[3][0].add(new CNFRule(3,1,2)); // v3 -> v1 v2
		rule[4][1].add(new CNFRule(4,'a')); // v4 -> a
		rule[5][1].add(new CNFRule(5,'b')); // v5 -> b	
	}
	
	/**
	* Initializes this to be a CNF grammar which generates 0*10*, 
	* strings with exactly one '1'.
	* @post data fields of this CNF grammar are set accordingly
	*/
	protected void constructC4()
	{
		alpha = new Alphabet("01"); // alphabet symbols
		numVars = 4; // numVars
		startToEpsilon = false; // start -> epsilon not a rule
		
		rule = new Vector[numVars][2]; // array of Vectors for rules
		// Create the rule Vectors
		for(int i=0; i<numVars; i++)
			for(int j=0; j<2; j++)
				rule[i][j] = new Vector();

		// create & store the rules for this grammar
		rule[0][1].add(new CNFRule(0,'1')); // v0 -> 1
		rule[0][0].add(new CNFRule(0,1,2)); // v0 -> v1 v2		
		rule[0][0].add(new CNFRule(0,1,3)); // v0 -> v1 v3
		rule[0][0].add(new CNFRule(0,2,1)); // v0 -> v2 v1
		rule[1][0].add(new CNFRule(1,1,1)); // v1 -> v1 v1
		rule[1][1].add(new CNFRule(1,'0')); // v1 -> 0
		rule[2][1].add(new CNFRule(2,'1')); // v2 -> 1
		rule[3][0].add(new CNFRule(3,2,1)); // v3 -> v2 v1
	}
	
	/**
	 * Initializes this to be a CNF grammar which generates all palindromes 
	 * over the alphabet {0,1}.
	 * @post data fields of this CNF grammar are set accordingly
	 */
	protected void constructC5()
	{
		alpha = new Alphabet("01"); // alphabet symbols
		numVars = 6; // numVars
		startToEpsilon = true; // start -> epsilon IS a rule
		
		rule = new Vector[numVars][2]; // array of Vectors for rules
		// Create the rule Vectors
		for(int i=0; i<numVars; i++)
			for(int j=0; j<2; j++)
				rule[i][j] = new Vector();

		// create & store the rules for this grammar
		rule[0][1].add(new CNFRule(0,'0')); // v0 -> 0
		rule[0][1].add(new CNFRule(0,'1')); // v0 -> 1
		rule[0][0].add(new CNFRule(0,1,1)); // v0 -> v1 v1
		rule[0][0].add(new CNFRule(0,2,2)); // v0 -> v2 v2
		rule[0][0].add(new CNFRule(0,1,3)); // v0 -> v1 v3
		rule[0][0].add(new CNFRule(0,2,4)); // v0 -> v2 v4
		rule[1][1].add(new CNFRule(1,'0')); // v1 -> 0
		rule[2][1].add(new CNFRule(2,'1')); // v2 -> 1
		rule[3][0].add(new CNFRule(3,5,1)); // v3 -> v5 v1
		rule[4][0].add(new CNFRule(4,5,2)); // v4 -> v5 v2
		rule[5][1].add(new CNFRule(5,'0')); // v5 -> 0
		rule[5][1].add(new CNFRule(5,'1')); // v5 -> 1
		rule[5][0].add(new CNFRule(5,1,1)); // v5 -> v1 v1
		rule[5][0].add(new CNFRule(5,2,2)); // v5 -> v2 v2
		rule[5][0].add(new CNFRule(5,1,3)); // v5 -> v1 v3
		rule[5][0].add(new CNFRule(5,2,4)); // v5 -> v2 v4		
	}	
		
	// ** TEST METHOD **
	public static void main(String[] args) 
	{
		new CNF();				
	}
}