org.metasyntactic.math.automata
Class PushdownAutomata

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

public class PushdownAutomata
extends AbstractFiniteAutomata

FORMAL DEFINATION OF A PUSHDOWN AUTOMATON

The formal definition of a pushdown automaton is similar to that of a finite automaton, except for the stack. The stack is a device containing symbols drawn from some alphabet. The machine may use different alphabets for its input and its stack, so now we specify both an input alphabet Σ and a stack alphaber Γ.

At the heart of any formal definition of an automaton is the transition function, for that describes its behavior. Recall the Σε = Σ ∪ {ε} and Γε = Γ ∪ {ε}. The domain of the transition function i Q x Σε ✗ Γε. Thus the current state, next input symbol read, and top symbol of the stack determine the next move of a pushdown automaton. Either symbol may be ε causing the machine to move without reading a symbol from the from the stack.

For the range of the transition function we need to consider what to allow the automaton to do when it is in a particular situation. It may enter some new state and possibly write a symbol on the top of the stack. The function δ can indicate this action by returning a member of Q together with a member of Γε, that is, a member of Q x Γε. Because we allow nondeterminism in this model, a situation may have several legal moves. The transition function incorporates nondeterminism in the usual way, by returning a set of members of Q x Γε, that is, a member of P(Q x Γε). Putting it all together, our transition function δ takes the form δ : Q x Σε x Γε → P(Q x Γε).

A pushdown automaton is a 6-tuplr (Q, Σ, Γ, δ, q0, F), where Q, Σ, Γ, and F are all finite sets, and

  1. Q is the set of states,
  2. Σ is the input alphabet,
  3. Γ is the stack alphabet,
  4. δ : Q x Σε x Γ&epsilon → P(Q x Γε) is the transition function
  5. q0 ∈ Q is the start state, and
  6. F ⊂ Q is the set of accept states. NOTE!! A transition function is of the form: Input, Tuple, Ouput Input is the startState The Tuple is the symbol, and the object to pop Ouput is a Set containing Tuples. Each Tuple contains the ending state and the symbol to push

    See Also:
    Serialized Form

    Field Summary
    protected  Stack stack
               
    protected  java.util.Set stackAlphabet
               
     
    Fields inherited from class org.metasyntactic.math.automata.AbstractFiniteAutomata
    acceptStates, alphabet, cachedTable, decision, immedateDecisionPossible, startState, states, transitionFunction
     
    Constructor Summary
    PushdownAutomata(java.util.Set states, java.util.Set alphabet, java.util.Set stackAlphabet, TransitionFunction transitionFunction, java.lang.Object startState, java.util.Set acceptStates)
               
     
    Method Summary
     boolean accept(java.util.Iterator w)
              A pushdown automata M = (Q, Σ, Γ, δ q0, F) computes as follows.
    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

    stackAlphabet

    protected java.util.Set stackAlphabet

    stack

    protected Stack stack
    Constructor Detail

    PushdownAutomata

    public PushdownAutomata(java.util.Set states,
                            java.util.Set alphabet,
                            java.util.Set stackAlphabet,
                            TransitionFunction transitionFunction,
                            java.lang.Object startState,
                            java.util.Set acceptStates)
    Method Detail

    accept

    public boolean accept(java.util.Iterator w)
                   throws ParseException
    A pushdown automata M = (Q, Σ, Γ, δ q0, F) computes as follows. It accepts input w if w can be written as w = w1w2 … wm, where each wi ∈ Σε and sequences of states r0, r1, …, rm ∈ Q and strings s0, s1, …, sm ∈ Γ* exist that satisfy the next three conditions. The strings si represent the sequence of stack contents that M has on the accepting branch of the computation.
    1. r0 = q0 and s0 = ε. This condition signifies that M starts out properly, in the start state and with an empty stack.
    2. for i = 0, …, m - 1, we have (ri+1, b) ∈ δ(ri, wi+1, a), where si = at and si+1 = bt for some a, b ∈ Γε and t ∈ Γ*. This condition states that M moves properly according to the state, stack, and next input symbol.
    3. rm ∈ F. This condition states that an accept state occurs at the input end.

    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)
                     throws java.lang.Throwable
    java.lang.Throwable