org.metasyntactic.math.automata
Class GeneralizedNondeterministicFiniteAutomata

java.lang.Object
  |
  +--org.metasyntactic.math.automata.AbstractFiniteAutomata
        |
        +--org.metasyntactic.math.automata.GeneralizedNondeterministicFiniteAutomata
All Implemented Interfaces:
FiniteAutomata, java.io.Serializable

public class GeneralizedNondeterministicFiniteAutomata
extends AbstractFiniteAutomata

Generalized nondeterministic finite automata (GNFA) are simply nondeterministic finite automata wherein the transition arrows may have any regular expressions as labels, instead of only members of the alphabet or ε. The GNFA reads blocks of symbols from the input, not necessarily just one symbol at a time as in an ordinary NondeterministicFiniteAutomata. The GNFA moves along a transition arrow connecting two states by reading a block of symbols from the input, which themselves constitute a string described by the regular expression on that arrow. A GNFA is nondeterministic and so may have several different ways to process the same input string. It accepts its input if its processing can cause the GNFA to be in an accept state at the end of the input.

For convenience we require that GNFAs always have a special form that meets the following conditions:

A generalized nondeterministic finite automaton, (Q, Σ, δ, qstart, qaccept), is a 5-tuple where
  1. Q is the finite set of states
  2. Σ is the input alphabet
  3. δ: (Q - {qaccept}) X (Q - {qstart}) → R is the transition function
  4. qstart is the start state
  5. qaccept is the accept state

See Also:
Serialized Form

Field Summary
protected  java.lang.Object acceptState
           
 
Fields inherited from class org.metasyntactic.math.automata.AbstractFiniteAutomata
acceptStates, alphabet, cachedTable, decision, immedateDecisionPossible, startState, states, transitionFunction
 
Constructor Summary
GeneralizedNondeterministicFiniteAutomata(DeterministicFiniteAutomata dfa)
           
GeneralizedNondeterministicFiniteAutomata(java.util.Set states, java.util.Set alphabet, TransitionFunction transitionFunction, java.lang.Object startState, java.lang.Object acceptState)
           
 
Method Summary
 boolean accept(java.util.Iterator w)
          A GNFA accepts a string w in Σ* if w = w1w2…wk, where each wi is in Σ* and a sequence of states q0, q1, …, qk exists such that: q0 = qstart is the start state qk = qaccept is the accept state for each i, we have wi ∈ L(Ri), where Ri = δ(qi-1, qi); in other words, Ri is the expression on the arrow from qi-1 to qi.
static RegularExpression convert(DeterministicFiniteAutomata dfa)
           
static RegularExpression convert(GeneralizedNondeterministicFiniteAutomata gnfa)
          We use the procedure convert(G), which takes a GNFA and returns an equivalent RegularExpression.
static RegularExpression convert(NondeterministicFiniteAutomata nfa)
           
static void main(java.lang.String[] args)
           
 
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
 

Field Detail

acceptState

protected java.lang.Object acceptState
Constructor Detail

GeneralizedNondeterministicFiniteAutomata

public GeneralizedNondeterministicFiniteAutomata(java.util.Set states,
                                                 java.util.Set alphabet,
                                                 TransitionFunction transitionFunction,
                                                 java.lang.Object startState,
                                                 java.lang.Object acceptState)

GeneralizedNondeterministicFiniteAutomata

public GeneralizedNondeterministicFiniteAutomata(DeterministicFiniteAutomata dfa)
Method Detail

convert

public static RegularExpression convert(DeterministicFiniteAutomata dfa)

convert

public static RegularExpression convert(NondeterministicFiniteAutomata nfa)

convert

public static RegularExpression convert(GeneralizedNondeterministicFiniteAutomata gnfa)
We use the procedure convert(G), which takes a GNFA and returns an equivalent RegularExpression. This procedure uses recursion, which means that it calls itself. An infinite loop is avoided because the procedure calls itself only to process a GNFA that has one fewer state. The case where GNFA has two states is handled without recursion.

Parameters:
gnfa - The GNFA to convert to a RegularExpression
Returns:
A new RegularExpression equivalent to gnfa

accept

public boolean accept(java.util.Iterator w)
               throws ParseException
A GNFA accepts a string w in Σ* if w = w1w2…wk, where each wi is in Σ* and a sequence of states q0, q1, …, qk exists such that:
  1. q0 = qstart is the start state
  2. qk = qaccept is the accept state
  3. for each i, we have wi ∈ L(Ri), where Ri = δ(qi-1, qi); in other words, Ri is the expression on the arrow from qi-1 to qi.

Parameters:
w - A string over some alphabet Σ
Returns:
true if this machine accepts w
Throws:
ParseException - if along the way of testing for acceptance, an exception occurred over the format of w

main

public static void main(java.lang.String[] args)