

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object jpaul.Graphs.DiGraph<Vertex> jpaul.Graphs.LabeledDiGraph<State,A> jpaul.RegExps.NFA<State,A>
public abstract class NFA<State,A>
NFA
models a Nondeterministic Finite Automaton. This
class is generic over the type State
of the states and
over the type A
of the input symbols.
An NFA
is a special case of labeled digraph. As
such, it is defined in a similar way, using a (labeled) arc
navigator. To avoid unnecessary complications, we assume that one
a navigator is used to define an NFA
, the information
it returns never changes. This is almost always the case in
practice; if you want to play with dynamically changing
NFA
s, then you have to manually scrap your old
NFA
and build a new one every time a change happens.
Attempting to use this class with a dynamically changing navigator
will result in unspecified (read buggy) behaviour.
The "nondeterminism" means that we can have multiple
transitions with the same label coming out of a state; we can also
have null
labeled transitions, modeling
"epsilon"transitions from classic NFA theory (transitions that
don't consume any input symbol).
To define an NFA, the programmer should subclass this class and
implement a few methods: startState()
, _acceptStates()
, and one of LabeledDiGraph.getLabeledForwardNavigator()
or
LabeledDiGraph.getLabeledBiDiNavigator()
. The states of the resulting NFA are
those states that are reachable from the starting state (as for any
LabeledDiGraph
); the transitions are given by the (labeled)
navigator.
Excellent material on NFAs can be found in "Introduction to the Theory of Computation" by Michael Sipser.
Nested Class Summary  

static interface 
NFA.BigState<State>
Certain NFA transformations (ex: simplify() ) produce NFA s whose states are sets of
original states. 
Nested classes/interfaces inherited from class jpaul.Graphs.LabeledDiGraph 

LabeledDiGraph.LabeledBiDiNavigator<Vertex,Label>, LabeledDiGraph.LabeledForwardNavigator<Vertex,Label> 
Field Summary 

Fields inherited from class jpaul.Graphs.DiGraph 

CACHING 
Constructor Summary  

protected 
NFA()
Constructs a NFA . 
Method Summary  

protected abstract java.util.Collection<State> 
_acceptStates()
Needs to be implemented by subclasses to return the accepting states. 

java.util.Collection<State> 
acceptStates()
Returns the accepting states of this NFA. 

static

create(State startState,
java.util.Collection<State> acceptStates,
LabeledDiGraph.LabeledBiDiNavigator<State,A> lNav)
Returns a freshly constructed NFA . 

static

create(State startState,
java.util.Collection<State> acceptStates,
LabeledDiGraph.LabeledForwardNavigator<State,A> lFwdNav)
Returns a freshly constructed NFA . 

java.util.Collection<State> 
getRoots()
Returns a singleton consisting of the start state, the single root of this NFA (a particular case of LabeledDiGraph ). 

NFA<NFA.BigState<State>,A> 
simplify()
Returns a simplified NFA that accepts the same
strings as this NFA. 

abstract State 
startState()
Returns the starting state of this NFA. 

java.util.Collection<State> 
states()
Returns all states from this NFA. 

RegExp<A> 
toRegExp()
Returns a regular expression over the alphabet A ,
representing all strings accepted by this NFA. 

java.lang.String 
toString()
Returns a pretty rough text representation for debugging pruposes. 
Methods inherited from class jpaul.Graphs.LabeledDiGraph 

getForwardNavigator, getLabeledBiDiNavigator, getLabeledForwardNavigator, getNavigator 
Methods inherited from class jpaul.Graphs.DiGraph 

constructBiDiNavigator, dfs, dfs2, diGraph, diGraph, findPath, findPath, findPath, forAllVertices, getBiDiNavigator, getComponentDiGraph, numArcs, numVertices, reverseDiGraph, subDiGraph, transitivePred, transitivePred, transitivePredWithFrontier, transitiveSucc, transitiveSucc, transitiveSuccWithFrontier, union, vertices 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait 
Constructor Detail 

protected NFA()
NFA
. This constructor is meant to
be invoked by the constructors of the subclasses: it just
informs the superclass LabeledDiGraph
constructor that
caching is OK; the information provided by the
LabeledForwardNavigator
is expected to stay unchanged
(see toplevel comments for this class).
Method Detail 

public abstract State startState()
public final java.util.Collection<State> acceptStates()
_acceptStates()
, except those
that are unreachable from the starting state.
protected abstract java.util.Collection<State> _acceptStates()
acceptStates()
that take
into account only those accepting states that are reachable
from the starting state; it is OK for this method to return
unreachable states.
acceptStates()
public java.util.Collection<State> states()
public final java.util.Collection<State> getRoots()
LabeledDiGraph
).
getRoots
in class LabeledDiGraph<State,A>
public static <State,A> NFA<State,A> create(State startState, java.util.Collection<State> acceptStates, LabeledDiGraph.LabeledForwardNavigator<State,A> lFwdNav)
NFA
.
startState
 Starting state for the automaton.acceptStates
 Accepting states for the automaton. An
input string (=list) of A
s is accepted iff it can
lead the NFA
from the starting state into one of
these states.lFwdNav
 Forward navigator that defines the outgoing
transitions for each automaton state. We can have multiple
transitions with the same label out of a state; we can also
have null
labeled transitions, modeling
"epsilon"transitions from classic NFA theory (transitions
that don't consume any input symbol). If necessary, the
NFA
will compute a full, bidirectional
navigator.public static <State,A> NFA<State,A> create(State startState, java.util.Collection<State> acceptStates, LabeledDiGraph.LabeledBiDiNavigator<State,A> lNav)
NFA
. Like other
nfa
static method, but a full navigator is
passed. Therefore, the getLabeledBiDiNavigator()
of the
returned NFA (if invoked) does not need to compute one.
public RegExp<A> toRegExp()
A
,
representing all strings accepted by this NFA. Complexity:
cubic in the number of states of this NFA.
public NFA<NFA.BigState<State>,A> simplify()
NFA
that accepts the same
strings as this NFA. "Simplified" means equal or smaller
number of states. The states of the simplified automaton
correspond to disjoint sets of states from this automaton: we
place two states in the same big state iff for any input
string starting in any of the two states leads to the same
acceptance outcome. Complexity: polynomial (cubic?) in the
size of the original NFA.
public java.lang.String toString()
toString
in class LabeledDiGraph<State,A>


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 