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
-
Q is the set of states,
-
Σ is the input alphabet,
-
Γ is the stack alphabet,
-
δ : Q x Σε x Γ&epsilon
→ P(Q x Γε) is the transition function
-
q0 ∈ Q is the start state, and
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
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 java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
stackAlphabet
protected java.util.Set stackAlphabet
stack
protected Stack stack
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)
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.
-
r0 = q0 and s0 =
ε. This condition signifies that M starts out
properly, in the start state and with an empty stack.
-
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.
-
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