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:

• The start state has transitions arrows going to every other state but no arrows coming in from any other state.
• There is only a single accept state, and it has arrows coming in from every other state but no arrows going to any other state. Furthermore, the accept state is not the same as the start state.
• Except for the start and accept states, one arrow goes from every state to every other state and also from each state to itself.

A generalized nondeterministic finite automaton, (Q, Σ, δ, q_start, q_accept), is a 5-tuple where

1. Q is the finite set of states
2. Σ is the input alphabet
3. δ: (Q - {q_{accept}) X (Q - {qstart}) → R is the transition function}
4. q_start is the start state
5. q_{accept 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 = w₁w₂…w_k, where each w_i is in Σ^* and a sequence of states q₀, q₁, …, q_k exists such that:

1. q₀ = q_start is the start state
2. q_k = q_accept is the accept state
3. for each i, we have w_i ∈ L(R_i), where R_i = δ(q_i-1, q_i); in other words, R_i is the expression on the arrow from q_i-1 to q_i.

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)