package TheoryLabs;
import java.util.Vector;
/**
 * Deterministic Finite Automaton.
 * 
 * <BR><BR>A dfa has a non-empty, finite set of states Q; an alphabet 
 * S; a transition function d which maps Q x S to Q; a unique "start" 
 * state; and zero or more "final" states.  The language L which is 
 * accepted by the dfa is the set of all strings s in S* which direct 
 * the dfa from "start" to any "final" state (according to the 
 * transition function d).
 * 
 * <BR><BR>Data Fields: 
 * In the DFA class we represent a DFA's transition function as a 
 * 2-dimensional array of integers.  Suppose the DFA has n states and m   
 * alphabet symbols. For any integer i from 0 through n-1 and any integer 
 * j from 0 through m-1, transition[i][j] indicates where to transition 
 * to (from state i) on reading the j-th alphabet symbol.  A 1-dimensional  
 * boolean array "isFinal" is used to indicate which states (if any) are  
 * final. In addition, each DFA has a Vector (stateLabel) of Strings to 
 * label the states, an Alphabet (alpha) of input symbols, a counter 
 * (numStates) for |Q|, and a variable start state (start).
 * 
 * <BR><BR>Methods: 
 * The DFA class has methods for generating the language of all strings 
 * accepted by the DFA (in lexicographic order, up through strings of the
 * specified length n), for testing whether or not a given input string 
 * is accepted by the DFA, for demonstrating the Pumping Lemma for 
 * Regular Languages on a given language string, and for pruning 
 * inaccessible states from the DFA.
 * 
 * <BR><BR>Note: From the user's point of view, states are referred to by label.  
 * Internally, states are numbered 0,1,2,... where 0 is not necessarily the start
 * state.
 * 
 * @author Barbara Wahl
 * @version Fall 2007
 */
public class DFA {
	// ** DATA FIELDS **
	/**
	 * number of states
	 */
	protected int numStates;
	
	/**
	 * list of labels for the states
	 */	
	protected Vector stateLabel;  
	
	/**
	 * Alphabet of input symbols
	 */
	protected Alphabet alpha;
	
	/**
	 * transition[i][j] tells where to transition 
	 * to (from state i) on reading the j-th alphabet symbol
	 */
	protected int[][] transition; 
	
	/**
	 * boolean array to designate final states
	 */
	protected boolean[] isFinal;
	
	/**
	 * start state
	 */
	protected int start;		
	
	/**
	 * 6-parameter constructor.
	 * @param n number of states
	 * @param L String array of state labels
	 * @param startL String label for the start state
	 * @param a String representation of the input alphabet
	 * @param t array representation of the transition function
	 * @param f boolean array to determine final states
	 * @pre n > 0
	 * @pre L is an array containing n non-null String objects
	 * @pre startL equals one of the strings in L
	 * @pre a is a non-empty String with no repeated characters or 
	 * whitespace
	 * @pre t has dimensions n by a.length()
	 * @pre every integer i in array t satisfies 0 <= i < n
	 * @post constructs an n-state DFA with alphabet a and transition 
	 * array t, state labels given by L, and final states given by f
	 * @post deep copies are made of all the arguments so that subsequent
	 * changes to any of these arguments will not affect the DFA constructed
 	 * by this method
	 */
	public DFA(int n, String[] L, String startL, String a, int[][] t, boolean[] f)
	{
		// use "Assert.pre" to check the precondition: n > 0
		// ???

		// initialize numStates	
		// ???
		
		// allocate and initialize stateLabel array (deep copy of L)	
		// ???	
		
		// use "Assert.pre" to check the precondition: startL equals one of the 
		// strings in L
		// ???

		// initialize start	
		// ???		
		
		// initialize alpha
		// ???

		// allocate and initialize transition array (deep copy of t)
		// (check the precondition: t[i][j] >= 0 && t[i][j] < n while
		// copying)	
		// ???	
		
		// allocate and initialize isFinal array (deep copy of f)	
		// ???
	}
	
	// ** PUBLIC METHODS **
	/**
	 * Tests whether this DFA accepts a given String.
	 * @param inString the String to be tested
	 * @return true iff this DFA accepts inString
	 * @pre inString is non-null
	 */		
	public boolean accepts(String inString)
	{		
		// Step 1:  Convert inString to an int array where each char is
		// represented by its position in the alphabet (return false
		// if find any symbols which are not in the alphabet)
		// ???
				
		// Step 2:  Run the DFA on s to determine which state it is
		// in after reading inString
		// ???
		
		// Step 3:  Return result (does the DFA stop at a final state?)
		// ???
	}
	
	/**
	 * Returns the language accepted by this DFA, thru a given max length.
	 * @param n maximum string length
	 * @return Vector containing the language accepted by this DFA, in lexicographic 
	 * order, up through strings of length n (returns null if n < 0)
	 */
	public Vector getLanguage(int n)
	{
		// handle case n < 0
		// ???

		// handle case n >= 0		
		Vector v = alpha.getLanguage(n); // v holds alpha* up through length n

		// use "accepts" to remove un-accepted strings from v
		// ???

		return v;
	}

	/**
	 * Prints the language accepted by this DFA, thru a given max length.
	 * @param n maximum string length
	 * @post prints the language accepted by this DFA, in lexicographic 
	 * order, up through strings of length n 
	 * @post prints nothing if n < 0
	 * @post prints "<empty language>" if n >= 0 and no strings of length
	 * n or less are accepted
	 */
	public Vector printLanguage(int n)
	{
		// handle case n < 0
		// ???
		
		// handle case n >= 0 
		// ???
	}
	
	
	/**
	 * Returns the set of state numbers of all final states.
	 * @return an IntSet containing the state numbers of all final
	 * states
	 */
	public IntSet finalStates()
	{
		IntSet s = new IntSet();
		// ???
		return s;
	}

	/**
	 * Pretty-prints the DFA transitions.
	 * @post prints each transition on its own line in the form 
	 * "(from,x) -> to", where "from" and "to" are state names 
	 * and x is an input symbol
	 */
	public void printTransitions()
	{
		// ???				
	}

	/**
	 * Pretty-prints the DFA specifications.
	 */
	public void printDFA()
	{
		// report numStates
		// ???
		
		// report alphabet
		// ???	
		
		// report starting state
		// ???
		
		// report final states
		// ???	
		
		// report transitions
		// ???	
	}

	 /**
	 * Returns the label for a given state number.
	 * @param i the state number
	 * @return the label for state i
	 * @pre i is a valid state number
	 */
	public String stateName(int i)
	{
		// ???
	}

	/** Returns the index of a given String in the stateLabel vector.
	 * @param s state label
	 * @return int i such that s equals stateLabel.elementAt(i), or -1
	 * if not found
	 * @pre s is not null
	 */
	public int stateNumber(String s)
	{
		// ???
	}

	/**
	 * Tests whether a given String is a valid state label.
	 * @param s String to be tested
	 * @return true iff s is contained in the stateLabel vector
	 * @pre s is not null
	 */
	public boolean validLabel(String s)
	{
		// ???
	}	
	
	/**
	 * Tests whether a given int is in the proper range to be a state
	 * number.
	 * @param i int value to be tested
	 * @return true iff 0 <= i < numStates
	 */
	public boolean validState(int i)
	{
		// ???
	}
	
	// ** TEST METHOD **
	public static void main(String[] args) 
	{
		// ???
	}
}