org.metasyntactic.math.automata
Class NondeterministicFiniteAutomata

java.lang.Object
  |
  +--org.metasyntactic.math.automata.AbstractFiniteAutomata
        |
        +--org.metasyntactic.math.automata.NondeterministicFiniteAutomata
All Implemented Interfaces:
FiniteAutomata, java.io.Serializable
Direct Known Subclasses:
DeterministicFiniteAutomata

public class NondeterministicFiniteAutomata
extends AbstractFiniteAutomata

FORMAL DEFINITION OF A NONDETERMINISTIC FINITE AUTOMATAON

The formal definition of a nondeterministic finite automaton is silmilar to that of a deterministic finite automaton. Both have states, an input alphabet, a transition function, a start state, and a collection of accept states. However, they differ in one essential way:
in the type of transition function. In a DFA the transition function takes a state and an input symbol and produces the next state. In an NFA the transition function takes a state and an input symbol or the empty string and produces the set of possible next states. In order to write the formal definition, we need to set up some additional notation. For any set Q we write P(Q) to be the collection of all subsets of Q. Here P(Q) is called the power set of Q. For any alphabet Σ we write Σε to be Σ∪{ε}.

Now we can easily write the formal description of the type of the transition function in an NFA. It is δ:Q x Σε→P(Q), and we are ready to give the formal definition.

A nondeterministic finite automaton is a 5-tuple (Q, Σ, δ, q0, F), where

  1. Q is a finite set of states,
  2. Σ is a finite alphabet,
  3. δ:Q x Σε→P(Q) is the transition function,
  4. q0∈Q is the start state, and
  5. F⊆Q is the set of accept states

See Also:
Serialized Form

Nested Class Summary
protected static class NondeterministicFiniteAutomata.DFAState
          Used to compress DFA states in toDeterministicFiniteAutomata
 
Field Summary
 
Fields inherited from class org.metasyntactic.math.automata.AbstractFiniteAutomata
acceptStates, alphabet, cachedTable, decision, immedateDecisionPossible, startState, states, transitionFunction
 
Constructor Summary
protected NondeterministicFiniteAutomata()
          For subclasses only
  NondeterministicFiniteAutomata(java.util.Set states, java.util.Set alphabet, TransitionFunction transitionFunction, java.lang.Object startState, java.util.Set acceptStates)
          Construct a new NondeterministicFiniteAutomata
  NondeterministicFiniteAutomata(java.util.Set states, java.util.Set alphabet, TransitionFunction transitionFunction, java.lang.Object startState, java.util.Set acceptStates, java.util.Map symbolToClasses)
          NFA's can be modified to accept symbol classes so as to compress tables and also to handle abstract concepts such as "any character".
 
Method Summary
 boolean accept(java.util.Iterator iterator)
          The formal definition of computation for a NondeterministicFiniteAutomata also is similar to that for a DeterministicFiniteAutomata.
 boolean accept(java.util.Iterator iterator, java.util.Map symbolToClasses)
           
 java.util.Set eClosure(java.lang.Object start)
          Set of NFA states reachable from NFA state 'start' on ε-transitions alone.
 java.util.Set eClosure(java.util.Set T)
          Set of NFA states reachable from some NFA state s in T on ε-transitions alone
protected  void init()
           
 java.util.Set move(java.util.Set states, java.lang.Object symbol, java.util.Map symbolToClasses)
          Set of NFA states to which there is a transition on input symbol 'symbol' from some NFA state s in 'states'
 DeterministicFiniteAutomata toDeterministicFiniteAutomata()
          Converts this NFA to a DFA using the 'subset construction method'
 DeterministicFiniteAutomata toDeterministicFiniteAutomata(boolean compress)
          Converts this NFA to a DFA using the 'subset construction method'
 
Methods inherited from class org.metasyntactic.math.automata.AbstractFiniteAutomata
getAcceptStates, getAlphabet, getStartState, getStates, getTransitionFunction, toStateTable, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

NondeterministicFiniteAutomata

protected NondeterministicFiniteAutomata()
For subclasses only


NondeterministicFiniteAutomata

public NondeterministicFiniteAutomata(java.util.Set states,
                                      java.util.Set alphabet,
                                      TransitionFunction transitionFunction,
                                      java.lang.Object startState,
                                      java.util.Set acceptStates)
Construct a new NondeterministicFiniteAutomata

Parameters:
states - Q is a finite set of states
alphabet - Σ is a finite alphabet
transitionFunction - δ:Q x Σε→P(Q) is the transition function
startState - q0∈Q is the start state
acceptStates - F⊆Q is the set of accept states

NondeterministicFiniteAutomata

public NondeterministicFiniteAutomata(java.util.Set states,
                                      java.util.Set alphabet,
                                      TransitionFunction transitionFunction,
                                      java.lang.Object startState,
                                      java.util.Set acceptStates,
                                      java.util.Map symbolToClasses)
NFA's can be modified to accept symbol classes so as to compress tables and also to handle abstract concepts such as "any character". By passing in a mapping from the symbols that will be read in to the respective character class, an NFA can achienve this effect. Note: overlapping character class ranges are not implemented for DFAs, so converting this NFA to a DFA is not supported.

Parameters:
states - Q is a finite set of states
alphabet - Σ is a finite alphabet
transitionFunction - δ:Q x Σε→P(Q) is the transition function
startState - q0∈Q is the start state
acceptStates - F⊆Q is the set of accept states
Method Detail

init

protected void init()

toDeterministicFiniteAutomata

public DeterministicFiniteAutomata toDeterministicFiniteAutomata()
Converts this NFA to a DFA using the 'subset construction method'

Returns:
the Deterministic version of this Finite Automata

toDeterministicFiniteAutomata

public DeterministicFiniteAutomata toDeterministicFiniteAutomata(boolean compress)
Converts this NFA to a DFA using the 'subset construction method'

Parameters:
compress - Increases computation time required to construc the DFA but returns a DFA using less memory
Returns:
the DFA equivalent of this NFA

accept

public boolean accept(java.util.Iterator iterator)
The formal definition of computation for a NondeterministicFiniteAutomata also is similar to that for a DeterministicFiniteAutomata. Let N = (Q, Σ, δ, q0, F) be an NondeterministicFiniteAutomata and w a string over the alphabet Σ. Then we say that N accepts w if we can write w as w = y1y2…ym, where each yi is a member of Σε and a sequence of states r0, r1, …, rm exists in Q with the following conditions:
  1. r0 = q0,
  2. ri+1 ∈ δ(ri, yi+1), for i = 0, …, m - 1, and
  3. rm ∈ F.
Condition 1 says that the machine starts out in the start state. Condition 2 says that state ri+1 is one of the allowable next states when N is in state ri and reading yi+1. Observe that δ(ri, yi+1) is the set of allowable next states and so we say that ri+1 is a member of that set. Finally, condition 3 says that the machine accepts its input if the last state is an accept state.

Parameters:
iterator - A string over some alphabet Σ
Returns:
true if this machine accepts w

accept

public boolean accept(java.util.Iterator iterator,
                      java.util.Map symbolToClasses)

eClosure

public java.util.Set eClosure(java.lang.Object start)
Set of NFA states reachable from NFA state 'start' on ε-transitions alone.

Parameters:
start - The state to find the eClosure of
Returns:
the set of all states reachable from start on ε-transitins alone

eClosure

public java.util.Set eClosure(java.util.Set T)
Set of NFA states reachable from some NFA state s in T on ε-transitions alone

Parameters:
T - the set of states to find the eClosure of
Returns:
the eClosre of the set T

move

public java.util.Set move(java.util.Set states,
                          java.lang.Object symbol,
                          java.util.Map symbolToClasses)
Set of NFA states to which there is a transition on input symbol 'symbol' from some NFA state s in 'states'

Parameters:
states - The states to move from
Returns:
The set of states that one can move to from states on symbols