|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object finiteAutomata.DFA
public class DFA
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.
Field Summary | |
---|---|
protected Alphabet |
alpha
Alphabet of input symbols |
protected boolean[] |
isFinal
boolean array to designate final states |
protected int |
numStates
number of states |
protected int |
start
start state |
protected java.util.Vector |
stateLabel
list of labels for the states |
protected int[][] |
transition
transition[i][j] tells where to transition to (from state i) on reading the j-th alphabet symbol |
Constructor Summary | |
---|---|
DFA()
0-parameter constructor, uses console input. |
|
DFA(int n,
java.lang.String[] L,
java.lang.String startL,
java.lang.String a,
int[][] t,
boolean[] f)
6-parameter constructor. |
Method Summary | |
---|---|
boolean |
accepts(java.lang.String inString)
Tests whether this DFA accepts a given String. |
IntSet |
accessible()
Returns all the states which are reachable from start. |
IntSet |
accessible(IntSet S,
int steps)
Returns all the states which are reachable from a given set of states in a given number of steps. |
protected void |
changeTransitionDialog()
Changes one transition based on user input. |
protected void |
constructD1()
Initializes this to be the DFA corresponding to Sipser, Figure 1.4. |
protected void |
constructD2()
Initializes this to be the DFA corresponding to Sipser, Figure 1.8. |
protected void |
constructD3()
Initializes this to be the DFA corresponding to Sipser, Figure 1.10. |
protected void |
constructD4()
Initializes this to be the DFA corresponding to Sipser, Figure 1.12. |
protected void |
constructD5()
Initializes this to be the DFA corresponding to Sipser, Figure 1.14. |
protected void |
constructD6()
Initializes this to be the DFA corresponding to Sipser, Figure 1.22. |
protected int |
constructorMenu()
Displays constructor menu options until user makes a valid choice. |
IntSet |
finalStates()
Returns the set of state numbers of all final states. |
java.util.Vector |
getLanguage(int n)
Returns the language accepted by this DFA, thru a given max length. |
static void |
main(java.lang.String[] args)
|
protected boolean |
menuHandler(int choice)
Takes the appropriate action based on constructorMenu options. |
protected void |
predefinedDialog()
Queries user which pre-defined DFA they will use. |
void |
printDFA()
Pretty-prints the DFA specifications. |
void |
printLanguage(int n)
Prints the language accepted by this DFA, thru a given max length. |
protected void |
printLanguageDialog()
Reports language of DFA up through user-specified max length. |
void |
printTransitions()
Pretty-prints the DFA transitions. |
void |
prune()
Eliminates inaccessible states. |
void |
pump(java.lang.String inString)
Demonstrates the Pumping Lemma for Regular Languages. |
protected boolean |
pumpTest(java.lang.String inString)
Prints header for pump report and tests the pumping preconditions. |
protected void |
queryAlphabet()
Initializes alpha according to user input. |
protected void |
queryFinal()
Initializes isFinal array according to user input. |
protected void |
queryLabels()
Obtains and initializes state labels based on user input. |
protected int |
queryNumStates()
Prints constructor menu banner and asks user how many states in DFA. |
protected boolean |
queryPredefined()
Asks user if they want to use a pre-defined DFA. |
protected int |
queryStart()
Asks user for start state. |
protected void |
queryTransition()
For each state and each alphabet symbol, asks user for destination. |
protected int |
queryValidState()
Queries user repeatedly to enter a state label. |
protected int |
queryValidSymbol()
Queries user repeatedly to enter an input symbol. |
protected int |
queryValidTransition(int i,
int j)
Queries user repeatedly to enter a valid destination state. |
java.lang.String |
stateName(int i)
Returns the label for a given state number. |
int |
stateNumber(java.lang.String s)
Returns the index of a given String in the stateLabel vector. |
protected void |
testEpsilonDialog()
Tests whether the epsilon string is accepted. |
protected void |
testingHandler()
Allows the user to repeatedly test strings or print this DFA's language. |
protected int |
testingMenu()
Presents testing menu options to user and obtains valid choice. |
protected void |
testStringDialog()
Queries user for string to test and reports back. |
boolean |
validLabel(java.lang.String s)
Tests whether a given String is a valid state label. |
boolean |
validState(int i)
Tests whether a given int is in the proper range to be a state number. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected int numStates
protected java.util.Vector stateLabel
protected Alphabet alpha
protected int[][] transition
protected boolean[] isFinal
protected int start
Constructor Detail |
---|
public DFA()
public DFA(int n, java.lang.String[] L, java.lang.String startL, java.lang.String a, int[][] t, boolean[] f)
n
- number of statesL
- String array of state labelsstartL
- String label for the start statea
- String representation of the input alphabett
- array representation of the transition functionf
- boolean array to determine final statesMethod Detail |
---|
public boolean accepts(java.lang.String inString)
inString
- the String to be tested
public IntSet accessible()
public IntSet accessible(IntSet S, int steps)
S
- IntSet of states from which to startsteps
- maximum number of transitions allowed
public IntSet finalStates()
public void printDFA()
public java.util.Vector getLanguage(int n)
n
- maximum string length
public void printLanguage(int n)
n
- maximum string lengthpublic void printTransitions()
public void prune()
public void pump(java.lang.String inString)
inString
- String to be pumpedpublic java.lang.String stateName(int i)
i
- the state number
public int stateNumber(java.lang.String s)
s
- state label
public boolean validLabel(java.lang.String s)
s
- String to be tested
public boolean validState(int i)
i
- int value to be tested
protected int constructorMenu()
protected boolean menuHandler(int choice)
choice
- user's desired action code
protected void testingHandler()
protected int testingMenu()
protected void testEpsilonDialog()
protected void testStringDialog()
protected void printLanguageDialog()
protected int queryNumStates()
protected void queryLabels()
protected boolean queryPredefined()
protected void predefinedDialog()
protected int queryStart()
protected void queryAlphabet()
protected void queryFinal()
protected int queryValidState()
protected int queryValidSymbol()
protected int queryValidTransition(int i, int j)
i
- current state numberj
- index of input symbol being read (position in alpha)
protected void queryTransition()
protected void changeTransitionDialog()
protected boolean pumpTest(java.lang.String inString)
inString
- String to be pumped
protected void constructD1()
protected void constructD2()
protected void constructD3()
protected void constructD4()
protected void constructD5()
protected void constructD6()
public static void main(java.lang.String[] args)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |