package TheoryLabs;
import java.util.Vector;
/**
* Deterministic Finite Automaton.
*
*
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).
*
*
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).
*
*
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.
*
*
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 "" 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;
}
// ** TEST METHOD **
public static void main(String[] args)
{
}
}