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, Σ, δ, q₀, 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. q₀∈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 - q₀∈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 - q₀∈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, Σ, δ, q₀, 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 = y₁y₂…y_m, where each y_i is a member of Σ_ε and a sequence of states r₀, r₁, …, r_m exists in Q with the following conditions:

1. r₀ = q₀,
2. r_i+1 ∈ δ(r_i, y_i+1), for i = 0, …, m - 1, and
3. r_m ∈ F.

Condition 1 says that the machine starts out in the start state. Condition 2 says that state r_i+1 is one of the allowable next states when N is in state r_i and reading y_i+1. Observe that δ(r_i, y_i+1) is the set of allowable next states and so we say that r_i+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