package finiteAutomata;
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;
// ** CONSTRUCTORS **
/**
* 0-parameter constructor, uses console input.
* @post constructs a DFA according to information obtained from the user
*/
public DFA()
{
// predefined = true if user wants to use a predefined object
boolean predefined = queryPredefined();
if(predefined)
predefinedDialog();
else
{ // get specs for user-defined DFA
numStates = queryNumStates();
stateLabel = new Vector(numStates); // Vector for state labels
queryLabels(); // get state labels from user
start = queryStart(); // initialize start state
queryAlphabet(); // initialize alphabet
isFinal = new boolean[numStates]; // allocate isFinal array
queryFinal(); // initialize isFinal array
// allocate & initialize transition array
transition = new int[numStates][alpha.size()];
queryTransition();
}
System.out.println("\nYour DFA has been constructed as follows:");
printDFA();
// repeatedly display menu, allowing user to change transitions,
// test strings, etc.
int choice = 0;
boolean done = false;
while(!done)
{
choice = constructorMenu(); // get user action choice
done = menuHandler(choice);
}
}
/**
* 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)
{
Assert.pre(n > 0, "n is positive");
numStates = n; // initialize numStates
stateLabel = new Vector(n); // allocate stateLabel array
for(int i=0; i= 0,
"startL is one of the String objects in L");
alpha = new Alphabet(a); // initialize alphabet
transition = new int[n][alpha.size()]; // allocate transition array
for(int i=0; i= 0 && t[i][j] < n,
"every integer i in array t satisfies 0 <= i < n");
transition[i][j] = t[i][j];
}
isFinal = new boolean[n]; // allocate isFinal array
System.arraycopy(f,0,isFinal,0,n); // copy f to isFinal
}
// ** 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)
int len = inString.length(); // input length
int[] charAt = new int[len];
if(!alpha.indexArray(inString,charAt))
return false;
// Step 2: Run the DFA on s
int currentState = start; // start state
for(int i=0; i= 0
*/
public IntSet accessible(IntSet S, int steps)
// note: accessible(S,0) = S [ base case ]
// note: if steps >= numStates,
// accessible(S,steps) = accessible(S,numStates-1)
{
if(S.isEmpty() || steps == 0) return S; // base case
Assert.pre(steps >= 0, "steps is non-negative");
Assert.pre(S.min() >= 0,
"each state i in S satisfies i >= 0");
Assert.pre(S.max() < numStates,
"each state i in S satisfies i < numStates");
if(steps > numStates-1) // these extra steps have no effect
steps = numStates-1;
// recursive case -- make progress!
IntSet previous = accessible(S,steps-1);
// add in any states one transition away from "previous"
int state;
for(int i=0; i" if n >= 0 and no strings of length
* n or less are accepted
*/
public void printLanguage(int n)
{
if(n < 0)
return; // prints nothing if n < 0
Vector v = this.getLanguage(n);
if(v.size() == 0)
{
System.out.println("");
return;
}
Alphabet.printLanguage(v);
}
/**
* 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()
{
int d; // the destination state
for(int i=0; i " + stateName(d));
}
}
/**
* Eliminates inaccessible states.
* @post eliminates all inaccessible states from this DFA; alpha
* is unchanged, but all the other data fields may change
*/
public void prune()
{
IntSet accessible = this.accessible(); // states reachable from start
int newSize = accessible.size();// number of states after pruning
if(newSize == numStates) // if no states are inaccessible...
return; // done!
// To finish, remove the inaccessible states and update the data fields
// NOTE: for each state x in "accessible", state # x in the
// old dfa will become state # accessible.indexOf(x)
// in the pruned dfa. For example, if
// accessible = [0,3,7] then state #0 becomes #0,
// state #3 becomes #1, and state #7 becomes #2.
// update stateLabel Vector, working tail to head
for(int i = numStates - 1; i >= 0; i--)
if(!accessible.contains(i)) // if state i is inaccessible
stateLabel.removeElementAt(i);
// store new transition and isFinal arrays in temp arrays
int[][] transTemp = new int[newSize][alpha.size()];
boolean[] finalTemp = new boolean[newSize];
int oldState;
for(int i=0; i= numStates
* @pre inString is accepted by this DFA
* @post prints info to the console to answer the following:
* (i) What is a "pumping length" p?
* (ii) What are values of x, y, and z which satisfy
* Sipser's Thm 1.70 (Pumping Lemma for
* Regular Languages)?
* (iii) Which strings are generated by pumping inString
* down or up? (xz, xyyz, xyyyz, xyyyyz, ...)
*/
public void pump(String inString)
{
// print heading & test pre-conditions (false if pre-conditions fail)
if(!pumpTest(inString)) return;
// visited[i] == -1 indicates that state i has not been visited;
// visited[i] == k means this DFA was in state i immediately before
// reading the kth character of inString
int[] visited = new int[numStates];
for(int i=0; i 0");
System.out.println(" note: |xy| = " + pos + " <= p");
System.out.print(" Pumping " + inString + " DOWN produces: ");
// if "y" is all of inString, then pumping down produces xz = epsilon
if(y.length() == inString.length())
System.out.println("epsilon");
else System.out.println(x.toString() + z.toString());
System.out.println(" Pumping " + inString + " UP produces: "
+ x + y + y + z + ", " // xyyz
+ x + y + y + y + z +", " // xyyyz
+ x + y + y + y + y + z + ", etc."); // xyyyyz
}
/**
* 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)
{
Assert.pre(this.validState(i),"i is a valid state number");
return (String)this.stateLabel.elementAt(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)
{
return stateLabel.indexOf(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)
{
return stateLabel.contains(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)
{
return (i >= 0 && i < numStates);
}
// ** MENU AND QUERY METHODS **
/**
* Displays constructor menu options until user makes a valid choice.
* @return choice (int from 1 thru 8)
*/
protected int constructorMenu()
{
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 DFA");
System.out.println(" 3 = print the language of this DFA");
System.out.println(" 4 = test a non-empty string");
System.out.println(" 5 = test the epsilon string");
System.out.println(" 6 = remove all inaccessible states");
System.out.println(" 7 = pump a string on this DFA");
System.out.println(" 8 = DONE with this DFA");
choice = Util.readNum();
if(1 <= choice && choice < 9)
valid = true;
}
return choice;
}
/**
* Takes the appropriate action based on constructorMenu options.
* @param choice user's desired action code
* @return true iff user is done with menu
* @pre 1 <= choice <= 8
*/
protected boolean menuHandler(int choice)
{
Assert.pre(1 <= choice && choice <= 8,
"1 <= choice <= 8");
switch (choice)
{
case 8: // quit from menu
System.out.println("Ciao!");
return true;
case 7: // pump
System.out.println("Enter an accepted string with " +
"length >= " + numStates);
this.pump(Util.readString());
break;
case 6: // prune
this.prune();
break;
case 5: // test epsilon string
this.testEpsilonDialog();
break;
case 4: // test a non-epsilon string
testStringDialog();
break;
case 3: // print language
printLanguageDialog();
break;
case 2: // print
printDFA();
break;
case 1: // change a transition
changeTransitionDialog();
}
return false;
}
/**
* Allows the user to repeatedly test strings or print this
* DFA's language.
* @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 testingHandler()
{
int n;
boolean done = false;
while(!done)
{
n = testingMenu(); // get menu choice from user
// take the appropriate action
switch (n) {
case 4: // quit
done = true;
break;
case 3: // print the FA's language
printLanguageDialog();
break;
case 2: // test a non-empty string
testStringDialog();
break;
case 1: // test epsilon string
testEpsilonDialog();
}
}
System.out.println("Good-bye!");
}
/**
* Presents testing menu options to user and obtains valid choice.
* @return choice (int from 1 thru 4)
*/
protected int testingMenu()
{
int n;
while(true) // present menu until valid choice is made
{
System.out.println("\nTesting Menu Options " +
"(enter your choice): " +
"\n 1 = test the empty string (epsilon) " +
"\n 2 = test a non-empty string " +
"\n 3 = print the FA's language " +
"\n 4 = DONE testing");
n = Util.readNum();
if(n>0 && n<=4) break;
System.out.println("TRY AGAIN!");
}
return n;
}
/**
* Tests whether the epsilon string is accepted.
* @post reports string length (0) and result
*/
protected void testEpsilonDialog()
{
System.out.print("input = epsilon, length = 0");
if(this.accepts(""))
System.out.println(" -- ACCEPTED!");
else
System.out.println(" -- REJECTED!");
}
/**
* Queries user for string to test and reports back.
* @post reports string length and result
*/
protected void testStringDialog()
{
String inString;
System.out.print("Enter the test string (no spaces): ");
inString = Util.readString();
System.out.print("input = " + inString +
", length = " + inString.length());
if(this.accepts(inString))
System.out.println(" -- ACCEPTED!\n");
else
System.out.println(" -- REJECTED!\n");
}
/**
* Reports language of DFA up through user-specified max length.
* @post queries user for max string length; reports language of
* DFA up through that max length
*/
protected void printLanguageDialog()
{
int n;
System.out.print("Enter a positive integer (maxLength): ");
n = Util.readNum();
this.printLanguage(n);
}
/**
* Prints constructor menu banner and asks user how many states in DFA.
* @return positive int obtained from user for numStates
*/
protected int queryNumStates()
{
int num; // temp storage for integer input
System.out.println("****** DFA CONSTRUCTOR MENU ******");
// ask user how many states; don't accept inappropriate input
num = 0; // an inappropriate input
while(num < 1)
{
System.out.print(">> Enter a positive integer " +
"(number of states): ");
num = Util.readNum();
}
return num;
}
/**
* Obtains and initializes state labels based on user input.
* @post user is prompted to enter a label for each state;
* responses are stored in stateLabel vector
*/
protected void queryLabels()
{
String inString;
for(int i=0; i> Enter a string to label state # "
+ i + ": ");
inString = Util.readString();
stateLabel.add(new String(inString));
}
}
/**
* Asks user if they want to use a pre-defined DFA.
* @return true iff user response begins with 'Y' or 'y'
*/
protected boolean queryPredefined()
{
System.out.print("Do you want to use a pre-defined DFA? Enter Y or N: ");
return Util.answerIsYes();
}
/**
* Queries user which pre-defined DFA they will use.
* @post initializes "this" DFA to match user choice
*/
protected void predefinedDialog()
{
int num;
while(true)
{
System.out.println("Choose a pre-defined DFA: ");
System.out.println(" 1 = Sipser, Figure 1.4");
System.out.println(" 2 = Sipser, Figure 1.8");
System.out.println(" 3 = Sipser, Figure 1.10");
System.out.println(" 4 = Sipser, Figure 1.12");
System.out.println(" 5 = Sipser, Figure 1.14");
System.out.println(" 6 = Sipser, Figure 1.22");
num = Util.readNum();
if(0 < num && num < 7)
break;
}
switch(num){
case 1:
constructD1();
break;
case 2:
constructD2();
break;
case 3:
constructD3();
break;
case 4:
constructD4();
break;
case 5:
constructD5();
break;
case 6:
constructD6();
}
}
/**
* Asks user for start state.
* @return valid state number (int from 0 thru numStates - 1)
*/
protected int queryStart()
{
String inString = " "; // temp storage for String input
System.out.print(">> Enter the label of the start state: ");
// get a valid state label
while(true)
{
inString = Util.readString();
if(validLabel(inString))
break;
else
System.out.print(">> TRY AGAIN! Enter the label" +
" of the start state: ");
}
return stateNumber(inString);
}
/**
* Initializes alpha according to user input.
* @post input Alphabet is initialized
*/
protected void queryAlphabet()
{
System.out.print(">> Enter a string with no spaces or " +
"repeated characters (alphabet): ");
alpha = new Alphabet(Util.readString());
}
/**
* Initializes isFinal array according to user input.
* @post final states are initialized as requested by user
*/
protected void queryFinal()
{
for(int i=0; i> Enter true or false -- is state \"" +
stateName(i) + "\" final? ");
isFinal[i] = Util.readBoolean();
}
}
/**
* Queries user repeatedly to enter a state label.
* @return corresponding state number of the first valid
* state label obtained
*/
protected int queryValidState()
{
String inString;
while(true)
{
System.out.print("Enter LABEL of state: ");
inString = Util.readString();
if(validLabel(inString))
break;
else System.out.println("TRY AGAIN!");
}
return stateNumber(inString);
}
/**
* Queries user repeatedly to enter an input symbol.
* @return corresponding symbol number of the first
* valid symbol obtained
*/
protected int queryValidSymbol()
{
char symbol;
String inString;
while(true)
{
System.out.print("Enter input symbol: ");
inString = Util.readString();
if(inString.length() == 1 && alpha.contains(inString.charAt(0)))
break;
}
symbol = inString.charAt(0);
return alpha.indexOf(symbol);
}
/**
* Queries user repeatedly to enter a valid destination state.
* @param i current state number
* @param j index of input symbol being read (position in alpha)
* @return destination state number (int from 0 thru numStates - 1)
* @pre 0 <= i < numStates and 0 <= j < alpha.size()
*/
protected int queryValidTransition(int i, int j)
{
Assert.pre(0 <= i && i < numStates,
"0 <= i < numStates");
Assert.pre(0 <= j && j < numStates,
"0 <= j < numStates");
String inString;
while(true)
{
System.out.print(">> In state \"" + stateName(i) +
"\", on input symbol " + alpha.charAt(j) +
", go to (enter LABEL of next state): ");
inString = Util.readString();
if(validLabel(inString))
break;
else System.out.println(">> TRY AGAIN! ");
}
return stateNumber(inString);
}
/**
* For each state and each alphabet symbol, asks user for destination.
* @post transition array is filled with valid state numbers as given
* by user
*/
protected void queryTransition()
{
int toState;
// Discover, for each state and each alphabet symbol, where to
// go? Use responses to initialize transition array.
for(int i=0; i " + stateName(k) + " has "
+ "been recorded");
}
// ** PUMPTEST METHOD (TO SUPPORT PUMP METHOD) **
/**
* Prints header for pump report and tests the pumping preconditions.
* @param inString String to be pumped
* @return true iff inString.length() >= numStates and inString
* is accepted
* @post (1) prints header for "pump" report
* (2) reports error if inString.length() < numStates
* (3) reports error if inString is not accepted
*/
protected boolean pumpTest(String inString)
{
System.out.println("\n>> Trying to PUMP \"" + inString +
"\" on current FA...");
System.out.println("A sufficient pumping length is p = " +
numStates);
// return false if inString is too short or is not accepted ...
if(inString.length() < numStates)
{
System.out.println("ERROR: \"" + inString + "\" is too SHORT;" +
" it's not guaranteed to be pumpable.");
System.out.println("(The Pumping Lemma only applies to " +
"strings which are \"long\".)");
return false;
}
if(!this.accepts(inString))
{
System.out.println("ERROR: \"" + inString + "\" is NOT ACCEPTED "
+ "by this FA, so it is not pumpable.");
System.out.println("(The Pumping Lemma only applies to strings "
+ "which are accepted by the FA.)");
return false;
}
return true;
}
// ** PRE-DEFINED DFA OBJECTS **
/**
* Initializes this to be the DFA corresponding to Sipser, Figure 1.4.
* @post all data fields are initialized to make a DFA equivalent to
* Sipser, Figure 1.4
*/
protected void constructD1()
{
numStates = 3;
start = 0;
alpha = new Alphabet("01");
// store state labels
stateLabel = new Vector();
stateLabel.add(new String("q1"));
stateLabel.add(new String("q2"));
stateLabel.add(new String("q3"));
// store transitions in array "t"
transition = new int[numStates][alpha.size()];
transition[0][0] = 0; // (q1,0)->q1
transition[0][1] = 1; // (q1,1)->q2
transition[1][0] = 2; // (q2,0)->q3
transition[1][1] = 1; // (q2,1)->q2
transition[2][0] = 1; // (q3,0)->q2
transition[2][1] = 1; // (q3,1)->q2
// store boolean values to set final states (q2)
isFinal = new boolean[numStates];
isFinal[1] = true;
}
/**
* Initializes this to be the DFA corresponding to Sipser, Figure 1.8.
* @post all data fields are initialized to make a DFA equivalent to
* Sipser, Figure 1.8
*/
protected void constructD2()
{
numStates = 2;
start = 0;
alpha = new Alphabet("01");
// store state labels
stateLabel = new Vector();
stateLabel.add(new String("q1"));
stateLabel.add(new String("q2"));
// store transitions
transition = new int[numStates][alpha.size()];
transition[0][0] = 0; // (q1,0)->q1
transition[0][1] = 1; // (q1,1)->q2
transition[1][0] = 0; // (q2,0)->q1
transition[1][1] = 1; // (q2,1)->q2
// store boolean values to set final states (q2)
isFinal = new boolean[numStates];
isFinal[1] = true;
}
/**
* Initializes this to be the DFA corresponding to Sipser, Figure 1.10.
* @post all data fields are initialized to make a DFA equivalent to
* Sipser, Figure 1.10
*/
protected void constructD3()
{
numStates = 2;
start = 0;
alpha = new Alphabet("01");
// store state labels
stateLabel = new Vector();
stateLabel.add(new String("q1"));
stateLabel.add(new String("q2"));
// store transitions
transition = new int[numStates][alpha.size()];
transition[0][0] = 0; // (q1,0)->q1
transition[0][1] = 1; // (q1,1)->q2
transition[1][0] = 0; // (q2,0)->q1
transition[1][1] = 1; // (q2,1)->q2
// store boolean values to set final states (q1)
isFinal = new boolean[numStates];
isFinal[0] = true;
}
/**
* Initializes this to be the DFA corresponding to Sipser, Figure 1.12.
* @post all data fields are initialized to make a DFA equivalent to
* Sipser, Figure 1.12
*/
protected void constructD4()
{
numStates = 5;
start = 0;
alpha = new Alphabet("ab");
// store state labels
stateLabel = new Vector();
stateLabel.add(new String("s"));
stateLabel.add(new String("q1"));
stateLabel.add(new String("q2"));
stateLabel.add(new String("r1"));
stateLabel.add(new String("r2"));
// store transitions
transition = new int[numStates][alpha.size()];
transition[0][0] = 1; // (s,a)->q1
transition[0][1] = 3; // (s,b)->r1
transition[1][0] = 1; // (q1,a)->q1
transition[1][1] = 2; // (q1,b)->q2
transition[2][0] = 1; // (q2,a)->q1
transition[2][1] = 2; // (q2,b)->q2
transition[3][0] = 4; // (r1,a)->r2
transition[3][1] = 3; // (r1,b)->r1
transition[4][0] = 4; // (r2,a)->r2
transition[4][1] = 3; // (r2,b)->r1
// store boolean values to set final states (q1, r1)
isFinal = new boolean[numStates];
isFinal[1] = true;
isFinal[3] = true;
}
/**
* Initializes this to be the DFA corresponding to Sipser, Figure 1.14.
* @post all data fields are initialized to make a DFA equivalent to
* Sipser, Figure 1.14
*/
protected void constructD5()
{
numStates = 3;
start = 0;
alpha = new Alphabet("R012");
// store state labels
stateLabel = new Vector();
stateLabel.add(new String("q0"));
stateLabel.add(new String("q1"));
stateLabel.add(new String("q2"));
// store transitions
transition = new int[numStates][alpha.size()];
transition[0][0] = 0; // (q0,R)->q0
transition[0][1] = 0; // (q0,0)->q0
transition[0][2] = 1; // (q0,1)->q1
transition[0][3] = 2; // (q0,2)->q2
transition[1][0] = 0; // (q1,R)->q0
transition[1][1] = 1; // (q1,0)->q1
transition[1][2] = 2; // (q1,1)->q2
transition[1][3] = 0; // (q1,2)->q0
transition[2][0] = 0; // (q2,R)->q0
transition[2][1] = 2; // (q2,0)->q2
transition[2][2] = 0; // (q2,1)->q0
transition[2][3] = 1; // (q2,2)->q1
// store boolean values to set final states (q0)
isFinal = new boolean[numStates];
isFinal[0] = true;
}
/**
* Initializes this to be the DFA corresponding to Sipser, Figure 1.22.
* @post all data fields are initialized to make a DFA equivalent to
* Sipser, Figure 1.22
*/
protected void constructD6()
{
numStates = 4;
start = 0;
alpha = new Alphabet("01");
// store state labels
stateLabel = new Vector();
stateLabel.add(new String("q"));
stateLabel.add(new String("q0"));
stateLabel.add(new String("q00"));
stateLabel.add(new String("q001"));
// store transitions
transition = new int[numStates][alpha.size()];
transition[0][0] = 1; // (q,0)->q0
transition[0][1] = 0; // (q,1)->q
transition[1][0] = 2; // (q0,0)->q00
transition[1][1] = 0; // (q0,1)->q
transition[2][0] = 2; // (q00,0)->q00
transition[2][1] = 3; // (q00,1)->q001
transition[3][0] = 3; // (q001,0)->q001
transition[3][1] = 3; // (q001,1)->q001
// store boolean values to set final states (q2)
isFinal = new boolean[numStates];
isFinal[3] = true;
}
// ** TEST METHOD **
public static void main(String[] args)
{
new DFA(); // runs DFA menu
}
}