|
|||||||||
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 labeled 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 |
addNewStart()
Adds a new start state, shifting all other states to make room. |
Alphabet |
alpha()
Returns a copy of the Alphabet. |
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. |
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. |
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. |
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 (including epsilon transitions) in form "(i,x) -> j". |
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. |
void |
starClosure()
Replaces this NFA by its star closure. |
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 void printNFA()
public void printFinal()
public void printTransitions()
public int numStates()
public Alphabet alpha()
public boolean validState(int i)
i
- the integer to be tested
public IntSet getFinalSet()
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
public void printLanguage(int n)
n
- maximum string length to be printedprotected void predefinedDialog()
protected 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 |