|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object finiteAutomata.NFA
public class NFA
Nondeterministic Finite Automaton.
An nfa has a non-empty, finite set of states Q; an alphabet S;
a transition function d which maps Q x (S U {epsilon}) to P(Q); a
unique "start" state; and zero or more "final" states. Notice that in
an nfa, there can be zero, one, two, or multiple transitions from a
given state on a given alphabet symbol, and epsilon transitions are
also allowed (transitioning without processing an input symbol). The
language L which is accepted by the nfa is the set of all strings s
in S* which direct the nfa from "start" to any "final" state along at
least one branch of the computation entailed by the transition function
d. Though nfas seem quite different from dfas, it is a fact that they
have no additional expressive power: every nfa has an equivalent dfa
(a dfa which accepts the same language).
Data Fields:
NFA states are labelled 0, 1, 2, etc., where state 0 is always
the start state. There are data fields "numStates" for recording the
number of states in the NFA, and "alpha" for storing the NFA's alphabet
of input symbols. Final states are indicated with a boolean array,
"isFinal".
With n states and m alphabet symbols, there are n x m possible
inputs to the transition function (not counting epsilon transitions).
An output from the transition function has to specify a list of zero
or more destination states; we will represent this output with a
1-dimensional boolean array where "true" values indicate valid
transitions. Thus, each NFA has a 3-dimensional boolean "transition"
array: for each possible "from" state i, for each possible "to" state
j, for the kth alphabet symbol, transition[i][j][k] is "true" iff we
can transition from state i to state j on the kth alphabet symbol.
Epsilon transitions are recorded in a separate boolean array:
epsilon[i][j] is true iff we can transition from state i to state j
on epsilon.
Each NFA has an equivalent DFA "D" whose states are a
subset of the power set of {0,1,2,3,...,numStates-1}. Computations
on the NFA are simulated by the corresponding computations on the
equivalent DFA.
Field Summary | |
---|---|
protected Alphabet |
alpha
input symbols |
protected DFA |
D
an equivalent DFA |
protected boolean[][] |
epsilon
for epsilon transitions; epsilon[i][j] is true iff we can transition from state i to state j on epsilon |
protected boolean[] |
isFinal
to indicate final states |
protected int |
numStates
number of states (positive) |
protected boolean[][][] |
transition
for symbol-consuming transitions; transition[i][j][k] is true iff we can transition from state i to state j on the kth alphabet symbol. |
Constructor Summary | |
---|---|
NFA()
0-parameter constructor. |
|
NFA(int n,
java.lang.String a,
boolean[][][] t,
boolean[][] e,
boolean[] f)
5-parameter constructor. |
Method Summary | |
---|---|
boolean |
accepts(java.lang.String inString)
Tests whether this NFA accepts a given input string. |
protected void |
addEpsilonDialog()
Queries user regarding which epsilon transition to add. |
protected void |
addNewStart()
Adds a new start state, shifting all other states to make room. |
protected void |
addTransitionDialog()
Queries user regarding which symbol-consuming transition to add. |
Alphabet |
alpha()
Returns a copy of the Alphabet. |
protected void |
changeTransition(int n)
Takes action based on provided transition change choice code. |
protected int |
changeTransitionDialog()
Queries user regarding desired transition change. |
protected void |
constructN1()
Makes "this" into an NFA corresponding to Sipser, Figure 1.27. |
protected void |
constructN2()
Makes "this" into an NFA corresponding to Sipser, Figure 1.31. |
protected void |
constructN3()
Makes "this" into an NFA corresponding to Sipser, Figure 1.34. |
protected void |
constructN4()
Makes "this" into an NFA corresponding to Sipser, Figure 1.36. |
protected int |
constructorMenu()
Displays constructor menu options and prompts user to choose an action. |
protected boolean |
constructorMenuHandler(int choice)
Takes action based on the provided constructor menu choice code. |
DFA |
convertToDFA()
Returns a DFA which is equivalent to this NFA |
boolean[] |
dfaGetFinal()
Returns an array of boolean values for "isFinal" array of an equivalent DFA. |
int[][] |
dfaSetTransitions()
Returns an array of DFA transitions for an equivalent DFA. |
boolean[][] |
epsilon()
Returns a copy of the epsilon transition array. |
IntSet[] |
getE()
Returns the "E" array, where E[i] = set of all states reachable from state i in 0-or-more epsilon transitions. |
IntSet |
getE(IntSet set)
Returns set of all states which are reachable from at least one state in the given set via 0-or-more epsilon transitions. |
IntSet |
getFinalSet()
Returns the set of final states. |
boolean[] |
isFinal()
Returns a copy of the isFinal array. |
static void |
main(java.lang.String[] args)
|
int |
numStates()
Returns number of states. |
protected void |
predefinedDialog()
Queries user which of 4 pre-defined NFAs they will use. |
void |
printFinal()
Prints list of final states in this NFA. |
void |
printLanguage(int n)
Prints the language accepted by this NFA up through a given maximum length. |
void |
printNFA()
Pretty-prints this NFA's specifications. |
void |
printTransitions()
Prints all the transitions in form "(i,x) -> j". |
protected void |
queryAlphabet()
Queries user to obtain alphabet of input symbols. |
protected void |
queryFinal()
Queries user to determine which states are final. |
protected int |
queryNumStates()
Prints constructor menu heading, and queries user until valid (positive) number of states is obtained. |
protected boolean |
queryPredefined()
Asks user if they want to use a pre-defined NFA. |
IntSet |
reachable(int s,
char c)
Returns set of all states which are reachable from the given state on consuming the given input symbol. |
IntSet |
reachable(IntSet set,
char c)
Returns set of all states which are reachable from at least one state in the given set on consuming the given input symbol. |
protected void |
removeEpsilonDialog()
Queries user regarding which epsilon transition to remove. |
protected void |
removeTransitionDialog()
Queries user regarding which symbol-consuming transition to remove. |
protected int |
runMenu()
Displays run menu options and prompts user to make a choice of action. |
protected boolean |
runMenuHandler(int choice)
Takes action based on the provided run menu choice code. |
void |
starClosure()
Replaces this NFA by its star closure. |
protected void |
testingDialog()
Allows the user to repeatedly test strings on this NFA. |
boolean[][][] |
transition()
Returns a copy of the symbol-consuming transition array. |
boolean |
validState(int i)
Returns true if the given integer is in the correct range to be a state in this NFA. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected int numStates
protected Alphabet alpha
protected boolean[] isFinal
protected boolean[][][] transition
protected boolean[][] epsilon
protected DFA D
Constructor Detail |
---|
public NFA()
public NFA(int n, java.lang.String a, boolean[][][] t, boolean[][] e, boolean[] f)
n
- number of desired statesa
- input symbolst
- array of symbol-consuming transitionse
- array of epsilon transitionsf
- array to indicate final statesMethod Detail |
---|
public int numStates()
public Alphabet alpha()
public boolean validState(int i)
i
- the integer to be tested
public IntSet getFinalSet()
public boolean[][][] transition()
public boolean[][] epsilon()
public boolean[] isFinal()
protected boolean queryPredefined()
protected void predefinedDialog()
protected int queryNumStates()
protected void queryAlphabet()
protected void queryFinal()
protected int constructorMenu()
protected boolean constructorMenuHandler(int choice)
choice
- constructor menu choice code
protected int runMenu()
protected boolean runMenuHandler(int choice)
choice
- run menu choice code
protected int changeTransitionDialog()
protected void changeTransition(int n)
n
- transition change choice codeprotected void removeEpsilonDialog()
protected void removeTransitionDialog()
protected void addEpsilonDialog()
protected void addTransitionDialog()
public IntSet reachable(int s, char c)
s
- the current statec
- the input symbol to be read
public IntSet reachable(IntSet set, char c)
set
- current statesc
- the input symbol to be read
public IntSet[] getE()
public IntSet getE(IntSet set)
set
- current states
public int[][] dfaSetTransitions()
public boolean[] dfaGetFinal()
public DFA convertToDFA()
public void starClosure()
protected void addNewStart()
public boolean accepts(java.lang.String inString)
inString
- the String to be tested
protected void testingDialog()
public void printNFA()
public void printFinal()
public void printTransitions()
public void printLanguage(int n)
n
- maximum string length to be printedprotected void constructN1()
protected void constructN2()
protected void constructN3()
protected void constructN4()
public static void main(java.lang.String[] args)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |