Pushdown Automata
Robert M. Keller
April 2016
Wanted: A Machine Characterizing Context-Free Languages
Applications
Parsing a language, such as a programming language
Creating a grammar by starting with a machine viewpoint is sometimes easier.
A Proper Context-Free Language
Using a Single Stack: �PDA = Pushdown Automaton
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q0
a
b
b
c
b
b
a
(empty stack)
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q1
a
b
b
c
b
b
a
$
$ indicates otherwise-empty stack,
so the machine can test for that when
necessary.
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q1
b
b
c
b
b
a
a
The input symbols are pushed
as they are read.
$
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q1
$
b
c
b
b
a
b
The input symbols are pushed
as they are read.
a
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q1
a
$
c
b
b
a
b
… until a c is encountered in the input,
causing a change of control state
b
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q2
a
$
b
b
a
b
The control state is changed.
The c is not pushed.
b
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q2
a
$
b
a
In the new control state,
input symbols are matched against
the stack symbols, which are discarded.
A mismatch stops the process, as
no successor is specified.
b
b
a
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q2
a
$
a
Matching continues.
a
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q2
$
The input is empty. However, there
is no way to react to input emptiness
as such.
The machine can go to an accepting�state whenever the current control state
is q2 and $ is on top of the stack
(according to the way we have defined
δ in this case).
unread input
Movie of the PDA accepting a string in�{xcxR | x ∈ {a, b}*}
q3
$
q3 is the accepting state, so the original�input abbcbba is accepted.
Had the input been abbcbb only, the
input would not be accepted, because
$ would not have been on top of the
stack when the input became empty,
and q3 would not have been entered.
Pushdown Automata (PDAs)
PDAs in practice
PDA Historical
The PDA was invented by �Anthony Oettinger at Harvard, �my “academic grandfather”.
Robert Keller
http://genealogy.math.ndsu.nodak.edu/id.php?id=13305
PDA Defined: (Q, Σ, Γ , δ, q0, F)
Sipser’s Version:
Notation: Σε = Σ ∪ {ε}, Γε = Γ ∪ {ε}. �
PDA Diagram
The state is generally of the form (q, x, γ) ∈ Q x Σ* x Γ*,
i.e. (control-state, remaining input, stack-contents).�
Sometimes this state is called the configuration or instantaneous
description (ID), to distinguish it from the control state. �I prefer to call it the state, which is what it is.
The initial state is (q0, x, ε). We will describe δ presently.
q
b
a
a
a
b
a
a
a
c
$
a
Control state:
input (one-way read-only):
stack (two-way):
∈ Q
∈ Γ*
∈ Σ*
Generalized Version: 5-Tuple Notation
In lieu of δ: Q x Σε x Γε → subsets of Q x Γε
use a set of 5-tuples for more convenience.
q, x, y → q′, z q, q′ ∈ Q
x ∈ Σε is what is read from the input � (either a letter or nothing)
y ∈ Γ* is what is on the top of the stack and popped
z ∈ Γ* is what is pushed
JFLAP supports this model.
δ can also be described by a graph
q'
q
σ , γ → γ '
control state before
control state after
input symbol (or ε)
stack symbol after (or ε)
stack symbol before (or ε)
In lieu of (q’, γ’) ∈ δ(q, σ, γ)
Sipser’s vs. Other Models
I think that Sipser’s model was conceived with a certain proof in mind. It is definitely not the easiest to program.
Knowing that these models can be inter-converted means that we can have ease in programming as well as proof elegance.
PDA Acceptance
PDA Non-Acceptance
Empty-Stack Acceptance
Initial Stack Symbol
Other PDA Alternatives
Worksheet
Work out the 5-tuples for a pda recognizing the language {xcxR | x ∈ {a, b}*}.
PDA accepting {xxR | x ∈ {a, b}*}
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q1
a
b
b
b
b
a
$
$ indicates otherwise “empty” stack,
so the machine can test for that when
necessary.
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q1
b
b
b
b
a
a
Symbols from the input are pushed
as read.
$
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q1
$
b
b
b
a
b
Symbols from the input are pushed
as read.
a
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q1
$
b
b
a
b
At any point, such as this one,
the machine can “guess” that it’s
at the middle of the string and
switch modes (without necessarily
using any input).
If it makes the “wrong” guess, that
particular sequence will end up not
accepting. There only need to be at
least one correct guess.
b
a
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q2
$
b
b
a
b
In control state q2, the machine begins
matching the input against the stack.
b
a
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q2
b
a
b
Matching continues.
a
$
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q2
a
a
Matching continues.
Any mis-match would result
in no further transitions.
$
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q2
$
In state with $ on top of stack,
the machine can decide to accept
what it has seen so far.
That doesn’t mean that it accepts
an extension of that input, however.
Movie of the PDA accepting a string in
{xxR | x ∈ {a, b}*}
q3
$
State q3 is accepting.
The original input abbbba is accepted.
Worksheet
Work out the 5-tuples for the
{xxR | x ∈ {a, b}*} PDA.
PDA described by a graph
q2
q3
q1
a, ε → a
b, ε → b
c, ε → ε
a, a → ε
b, b → ε
ε, $ → $
q0
ε, ε → $
δ can also be described by “transition rules”
q1, a, ε → q1, a
q1, b, ε → q1, b
q1, ε, ε → q2, ε
q2, a, a → q2, ε
q2, b, b → q2, ε
q2, ε, $ → q3, $
Each rule is essentially a 5-tuple:�� current-state, input-read, stack-popped, next-state, stack-pushed
JFLAP Version of PDA
http://www.jflap.org/tutorial/pda/construct/
JFLAP defines a pushdown automaton M as the septuple �M = (Q, Σ, Γ, δ, qs, Z, F) where�
Example: Well-balanced Paren Strings
Input, Pop; Push
(Z is atop stack at start)
(Z is popped on acceptance)
Intentionally not accepted: ε, ()(), etc.
Running Examples
CFL Characterization Theorem
The ⇒ and ⇒* notation for PDA states
A key property (“stack property”) of PDA’s:
Leftmost/Rightmost Derivation Nomenclature
Parallel Between CFG and PDA
Each derivation � S ⇒* x �in a CFG
corresponds to a series of moves �
(q, x, S) ⇒* (q′, ε, ε)
of a PDA accepting by empty stack.�
Left/Rightmost Derivations
A → V | V + A
V → a | b | c
leftmost: A ⇒ V+A ⇒ c+A⇒ c+V+A⇒ c+a+A⇒ c+a+V⇒ c+a+b�
rightmost: A ⇒ V+A ⇒ V+V+A ⇒ V+V+V ⇒ V+V+b ⇒ V+a+b ⇒ c+a+b
b
A
V + A
V + A
a
V
c
CFL → PDA Lemma
(No generality is lost.)
Proof of the CFL → PDA Lemma using �Top-Down, LL, or Produce-Match technique
Produce-Match technique continued
Example of CFG to PDA Transition Rules
Production Transition (top of stack at left)� q0, ε, ε → q1, S$ initial � S → (T q1, ε, S → q1, (T produce � S → (ST q1, ε, S → q1, (ST produce� S → (TS q1, ε, S → q1, (TS produce� S → (STS q1, ε, S → q1, (STS produce� T → ) q1, ε, T → q1, )
Extra rules: q1, (, ( → q1, ε match
q1, ), ) → q1, ε match
q1, $, ε → q2, ε accept� � q0 is initial, q2 is accepting
Derivation vs. Transition Sequence
State, Input, Stack Transitions
Derivation q0, ()(), ε init �S ⇒ q1, ()(), S$ produce S → (TS �(TS ⇒ q1, ()(), (TS$ match (� q1,)(), TS$ produce T → ) �()S ⇒ q1,)(), )S$ match ) � q1,(), S$ produce S → (T �()(T ⇒ q1,(), (T$ match (� q1,), T$ produce T → ) �()() q1,), )$ match )
q1, ε, $ accept
q2, ε, $
Derivation: S ⇒ (TS ⇒ ()S ⇒ ()(T ⇒ ()()
Another Way of Showing
Stack vs. Leftmost Derivation
S
S
S
T
(
S
T
(
S
T
S
(
S
T
(
S
T
S
(
)
S
T
(
S
T
S
(
)
T
(
S
T
(
S
T
S
(
)
T
(
)
S
T
(
S
T
S
(
)
T
(
)
)
Grammar
Produce-Match Version PDA in JFLAP
JFLAP Tests of Top-Down Version
A JFLAP-generated Tree for ()()
using Produce Match (LL)
A 2nd Proof of the CFG ⇒ PDA Lemma: �Bottom-Up, LR, or Shift-Reduce technique
These have the effect of shifting the input string onto the stack (and reversing it in the process).�
Example of Bottom-Up
Production Transitions� S → (T q0, ε, T( → q0, S� � T → S) q0, ε, )S → q0, T� � S → () q0, ε, )( → q0, S � S → SS q0, ε, SS → q0, S
shift transitions q0, (, ε → q0, ( � q0, ), ε → q0, )�� accept q0, ε, S → q1, ε � transitions q1, ε, $ → qa, $
Input | State | Stack Rule
(()()) | q0 | $ q0, (, ε → q0, (
(()()) | q0 | ($ q0, (, ε → q0, (�(()()) | q0 | (($ q0, ), ε → q0, )�(()()) | q0 | )(($ q0, ε, )( → q0, S�(()()) | q0 | S($ q0, (, ε → q0, (�(()()) | q0 | (S($ q0, ), ε → q0, )�(()()) | q0 | )(S($ q0, ε, )( → q0, S�(()()) | q0 | SS($ q0, ε, SS → q0, S�(()()) | q0 | S($ q0, ), ε → q0, )�(()()) | q0 | )S($ q0, )S, ε → q0, T�(()()) | q0 | T($ q0, T(, ε → q0, S�(()()) | q0 | S$ q0, ε, S → q1, ε�(()()) | q1 | $ q1, ε, $ → qa, $�(()()) | qa | $ accept
Derivation: S ⇒ (T ⇒ (S) ⇒ (SS) ⇒ (S()) ⇒ (()())
Shift-Reduce Version in JFLAP
JFLAP Shift-Reduce Acceptance
How these methods differ from actual parsers
LL(k) vs. LR(k)
PDA → CFG
PDA → CFG Lemma
Additional constraints are imposed on PDA M, without loss of generality:
but not both.
[If a transition does both, add an intermediate state and have it pop, then push. ��If a transition does neither, have it push an arbitrary symbol, then immediately pop it.]
Construction of G from M
We want �G to generate a terminal string x
iff
M goes from its initial state to accepting state with x as input, �with the stack empty before and after.
Construction (which is slightly more general than the main goal):
For each pair of states p, q in M, �define an auxiliary Apq in G.
We want:� � ∀x∈ Σ* [(p, x, ε) ⇒* (q, ε, ε) in M iff � Apq ⇒* x in G].�
How to achieve this?
Construction continued
Two Possibilities
stack size
amount of
input x read
A.
stack�becomes
empty
stack size
amount of
input x read
B.
stack �never�empty
in between
p
q
p
q
r
x
y
z
x = yz
(It may become empty �again and again.)
Simulating Transition Sequences with G
because x can be written yz, where �(p, yz, ε) ⇒* (r, z, ε) and (r, z, ε) ⇒* (q, ε, ε)
[which combine to (p, yz, ε) ⇒* (q, ε, ε)].
Simulating Transition Sequences with G
Note that x can be written ayb, where �(p, ayb, ε) ⇒* (r, yb, ε) and (r, z, ε) ⇒* (q, ε, ε)
[which combine to (p, yz, ε) ⇒* (q, ε, ε)].
Summary Construction of G
Proof that L(G) = L(M)
Claim 2.30 (Sipser):L(G) ⊆ L(M)
Claim 2.30 Induction, case A.
Claim 2.30 Induction, case B.
Claim 2.31 (Sipser) L(M) ⊆ L(G)
Sipser Proof vs. JFLAP
PDA to CFG as a way to get grammar�
PDA for L
JFLAP-Generated Grammar for L
Conversion of Grammar back to PDA Using LL (Produce-Match)
Conversion of Grammar back to PDA Using LR (Shift-Reduce)