jpaul.RegExps
Class NFA<State,A>

java.lang.Object
  extended by jpaul.Graphs.DiGraph<Vertex>
      extended by jpaul.Graphs.LabeledDiGraph<State,A>
          extended by jpaul.RegExps.NFA<State,A>

public abstract class NFA<State,A>
extends LabeledDiGraph<State,A>

NFA models a Non-deterministic 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 NFAs, 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 "non-determinism" 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.

Version:
$Id: NFA.java,v 1.17 2006/03/14 02:29:31 salcianu Exp $
Author:
Alexandru Salcianu

Nested Class Summary
static interface NFA.BigState<State>
          Certain NFA transformations (ex: simplify()) produce NFAs 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
<State,A> NFA<State,A>
create(State startState, java.util.Collection<State> acceptStates, LabeledDiGraph.LabeledBiDiNavigator<State,A> lNav)
          Returns a freshly constructed NFA.
static
<State,A> NFA<State,A>
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

NFA

protected NFA()
Constructs a 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 top-level comments for this class).

Method Detail

startState

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


acceptStates

public final java.util.Collection<State> acceptStates()
Returns the accepting states of this NFA. This method returns all states returned by _acceptStates(), except those that are unreachable from the starting state.


_acceptStates

protected abstract java.util.Collection<State> _acceptStates()
Needs to be implemented by subclasses to return the accepting states. NFA algorithms use 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.

See Also:
acceptStates()

states

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


getRoots

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

Specified by:
getRoots in class LabeledDiGraph<State,A>

create

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

Parameters:
startState - Starting state for the automaton.
acceptStates - Accepting states for the automaton. An input string (=list) of As 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, bi-directional navigator.

create

public static <State,A> NFA<State,A> create(State startState,
                                            java.util.Collection<State> acceptStates,
                                            LabeledDiGraph.LabeledBiDiNavigator<State,A> lNav)
Returns a freshly constructed 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.


toRegExp

public RegExp<A> toRegExp()
Returns a regular expression over the alphabet A, representing all strings accepted by this NFA. Complexity: cubic in the number of states of this NFA.


simplify

public NFA<NFA.BigState<State>,A> simplify()
Returns a simplified 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.


toString

public java.lang.String toString()
Returns a pretty rough text representation for debugging pruposes.

Overrides:
toString in class LabeledDiGraph<State,A>


Copyright 2005 Alexandru Salcianu - salcianu@alum.mit.edu