jpaul.RegExps
Class NFA<State,A>

java.lang.Object
  jpaul.Graphs.DiGraph<Vertex>
      jpaul.Graphs.LabeledDiGraph<State,A>
          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>