## 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

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