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

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`