COMP30026 Models of Computation – Pushdown Automata
COMP30026 Models of Computation
Pushdown Automata
Bach Le / Anna Kalenkova
Lecture Week 9
Semester 2, 2021
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 1 / 40
Leftmost derivation
Consider the grammar:
E → T | T + E
T → F | F ∗ T
F → 0 | 1 | . . . | 9 | ( E )
Here is the leftmost derivation for ( 3 + 7 ) ∗ 2:
E ⇒ T ⇒ F ∗ T ⇒ ( E ) ∗ T ⇒ ( T + E ) ∗ T
⇒ ( F + E ) ∗ T ⇒ ( 3 + E ) ∗ T ⇒ ( 3 + T ) ∗ T
⇒ ( 3 + F ) ∗ T ⇒ ( 3 + 7 ) ∗ T ⇒ ( 3 + 7 ) ∗ F
⇒ ( 3 + 7 ) ∗ 2
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 2 / 40
Pushdown Automata
The automata we saw so far were limited by their lack of memory.
A pushdown automaton (PDA) is a finite-state automaton, equipped
with a stack.
The language {aibi | i ≥ 0} is
not recognised by any DFA,
since it requires the ability of a
recogniser to remember how
many consecutive as have been
consumed from the input.
state
control
stack
a a b b
input
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 3 / 40
Pushdown Automata
The automata we saw so far were limited by their lack of memory.
A pushdown automaton (PDA) is a finite-state automaton, equipped
with a stack.
The language {aibi | i ≥ 0} is
not recognised by any DFA,
since it requires the ability of a
recogniser to remember how
many consecutive as have been
consumed from the input.
state
control
a
stack
a b b
input
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 4 / 40
Pushdown Automata
The automata we saw so far were limited by their lack of memory.
A pushdown automaton (PDA) is a finite-state automaton, equipped
with a stack.
The language {aibi | i ≥ 0} is
not recognised by any DFA,
since it requires the ability of a
recogniser to remember how
many consecutive as have been
consumed from the input.
state
control
a
a
stack
b b
input
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 5 / 40
Pushdown Automata
The automata we saw so far were limited by their lack of memory.
A pushdown automaton (PDA) is a finite-state automaton, equipped
with a stack.
The language {aibi | i ≥ 0} is
not recognised by any DFA,
since it requires the ability of a
recogniser to remember how
many consecutive as have been
consumed from the input.
state
control
a
stack
b
input
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 6 / 40
Pushdown Automata
The automata we saw so far were limited by their lack of memory.
A pushdown automaton (PDA) is a finite-state automaton, equipped
with a stack.
The language {aibi | i ≥ 0} is
not recognised by any DFA,
since it requires the ability of a
recogniser to remember how
many consecutive as have been
consumed from the input.
state
control
stack input
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 7 / 40
Fine but Important Points
Based on (1) input symbol, (2) top stack symbol, and (3) the current
state, PDA will decide which state to go to next, as well as, what
operation apply to the stack.
In one transition step, PDA reads a symbol from input and pops the
top stack symbol, or pushes to the stack, or both (replaces the top
stack symbol).
We shall consider the non-deterministic version of a PDA.
It may also ignore the input.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 8 / 40
Pushdown Automata Formally
A pushdown automaton is a 6-tuple (Q,Σ, Γ, δ, q0, F ) where
Q is a finite set of states,
Σ is the finite input alphabet,
Γ is the finite stack alphabet,
δ : Q × Σ
ǫ
× Γ
ǫ
→ P(Q × Γ
ǫ
) is the transition function,
q0 ∈ Q is the start state, and
F ⊆ Q are the accept states.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 9 / 40
Example Transitions
δ(q5, a, b) = {(q7, ǫ)} means:
If in state q5, when reading input symbol a, provided the top of the
stack holds ‘b’, consume the a, pop the b, and go to state q7.
δ(q5, ǫ, b) = {(q6, a), (q7, b)} means:
If in state q5, and if the top of the stack holds ‘b’, either replace that
b by a and go to state q6, or leave the stack as is and go to state q7.
In either case do not consume an input symbol.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 10 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
Q = {q0, q1, q2, q3};
Σ = {a, b};
Γ = {a, $};
δ(q0, ǫ, ǫ) = {(q1, $)},δ(q1, a, ǫ) = {(q1, a)},
δ(q1, b, a) = {(q2, ǫ)},δ(q2, b, a) = {(q2, ǫ)},
δ(q2, ǫ, $) = {(q3, ǫ)}, for other inputs δ returns ∅;
q0 = q0;
F = {q0, q3}.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 11 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
state
control
a a b b
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 12 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
state
control
$ a a b b
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 13 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
state
control
$
a
a b b
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 14 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
state
control
$
a
a
b b
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 15 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
state
control
$
a
b
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 16 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
state
control
$
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 17 / 40
PDA Example 1
This PDA recognises {anbn | n ≥ 0}:
q0 q1 q2 q3
ǫ, ǫ → $ b, a → ǫ ǫ, $ → ǫ
a, ǫ → a b, a → ǫ
state
control
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 18 / 40
Acceptance Precisely
The PDA (Q,Σ, Γ, δ, q0, F ) accepts input w iff w = v1v2 · · · vn with
each vi ∈ Σǫ, and there are states r0, r1, . . . , rn ∈ Q and strings
s0, s1, . . . , sn ∈ Γ
∗ such that
1 r0 = q0 and s0 = ǫ.
2 (ri+1, b) ∈ δ(ri , vi+1, a), si = at, si+1 = bt with a, b ∈ Γǫ and
t ∈ Γ∗
ǫ
.
3 rn ∈ F .
Note 1: There is no requirement that sn = ǫ, so the stack may be
non-empty when the machine stops (even when it accepts).
Note 2: Trying to pop an empty stack leads to rejection of input,
rather than “runtime error”.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 19 / 40
PDA Example 2
Let wR denote the string w reversed.
Let us design a PDA to recognise {wwR | w ∈ {0, 1}∗}, the set of
even-length binary palindromes:
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 20 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
1 0 0 1
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 21 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
$ 1 0 0 1
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 22 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
$
1
0 0 1
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 23 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
$
1
0
0 1
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 24 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
$
1
0
0 1
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 25 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
$
1
1
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 26 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
$
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 27 / 40
PDA Example 2
q0 q1 q2 q3
ǫ, ǫ → $ ǫ, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → 0
1, ǫ → 1
0, 0 → ǫ
1, 1 → ǫ
state
control
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 28 / 40
Progressive PDAs
A pushdown automaton (Q,Σ, Γ, δ, q0, F ) is progressive iff
∀q ∈ Q, ∀a ∈ Γ
ǫ
: δ(q, ǫ, a) = ∅.
A pushdown automaton is progressive if and only if each transition
step consumes exactly one input symbol.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 29 / 40
Deterministic PDAs
Is a deterministic PDA (a DPDA) as powerful as a PDA?
No. A DPDA can recognise the context-free
{wcwR | c ∈ Σ,w ∈ (Σ \ {c})∗}
but not the context-free {wwR | w ∈ Σ∗}.
Intuitively a deterministic machine cannot know when the middle of
the input has been reached. Suppose it gets input
00001100000000110000
A deterministic machine won’t know when to start popping the stack.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 30 / 40
Deterministic PDAs
A pushdown automaton (Q,Σ, Γ, δ, q0, F ) is deterministic
iff ∀q ∈ Q, ∀v ∈ Σ, ∀a ∈ Γ it holds that:
|δ(q, v , a)|+ |δ(q, ǫ, a)|+ |δ(q, v , ǫ)|+ |δ(q, ǫ, ǫ)| ≤ 1.
For any configuration there can be at most one of the four transitions.
A deterministic pushdown automaton (DPDA) never finds itself in a
position where it can make two different transition steps.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 31 / 40
CFLs Have PDAs as Recognisers
Given a context-free language L (in the form of a grammar), we can
find a PDA which recognises L.
And, every PDA recognises a context-free language.
We won’t prove the second claim, but the first claim can easily be
seen to hold.
Namely, given a CFG G , we show how to construct a PDA P such
that L(P) = L(G ).
The idea is to let the PDA use its stack to store a list of “pending”
recogniser tasks.
The construction does not give the cleverest PDA, but it always
works.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 32 / 40
From Context-Free Grammars to PDAs
Say B → xAy is a rule in G , and the PDA finds the symbol B on top
of its stack, it may pop B and push y , A, and x , in that order.
state
control
B
stack
x y y
input
state
control
x
A
y
stack
x y y
input
If it finds the terminal x on top of the stack, and x is the next input
symbol, it may consume the input and pop x .
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 33 / 40
From Context-Free Grammars to PDAs
Construct the PDA like this:
q
ǫ, ǫ → $ ǫ, ǫ → S ǫ, $ → ǫ
a, a → ǫ
with a self-loop from q for each terminal a
(S is the grammar’s start symbol).
For each rule A → α1 . . . αn,
add this loop from q to q:
q
ǫ,A → αnǫ, ǫ → α1
ǫ, ǫ → αi
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 34 / 40
Example Recogniser
For the grammar S → a S b b | b | ǫ
q
ǫ, ǫ → $ ǫ, ǫ → S ǫ, $ → ǫ
a, a → ǫ
b, b → ǫ
ǫ, S → b
ǫ, S → ǫ
ǫ, S → bǫ, ǫ → a
ǫ, ǫ → bǫ, ǫ → S
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 35 / 40
Pumping Lemma for CFLs
There are languages that are not context-free, and again there is a
pumping lemma that can be used to show (some) languages
non-context-free:
If A is context-free then there is a number p such that for any string
s ∈ A with |s| ≥ p, s can be written as s = uvxyz , satisfying
1 uv ixy iz ∈ A for all i ≥ 0
2 |vy | > 0
3 |vxy | ≤ p
We won’t prove this lemma, but we give two examples of its use.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 36 / 40
Pumping Example 1
A = {ww | w ∈ {0, 1}∗} is not context-free.
Assume it is, let p be the pumping length, take 0p1p0p1p.
By the pumping lemma, 0p1p0p1p = uvxyz , with uv ixy iz in A for all
i ≥ 0, and |vxy | ≤ p.
There are three ways that vxy can be part of
00. . .0011. . .1100. . .0011. . .11
If it straddles the midpoint, it has form 1n0m, so pumping down, we
are left with 0p1i0j1p, with i < p, or j < p, or both.
If it is in the first half, uv 2xy 2z will have pushed a 1 into the first
position of the second half.
Similarly if vxy is in the second half.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 37 / 40
Pumping Example 2
B = {anbncn | n ∈ N} is not context-free.
Assume it is, let p be the pumping length, and take apbpcp ∈ B .
By the pumping lemma, apbpcp = uvxyz , with uv ixy iz in B for all i .
Either v or y is non-empty (or both are).
If one of them contains two different symbols from {a, b, c} then
uv 2xy 2z has symbols in the wrong order, and so cannot be in B .
So both v and y must contain only one kind of symbol. But then
uv 2xy 2z can’t have the same number of as, bs, and cs.
In all cases we have a contradiction.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 38 / 40
Closure Properties for CFLs
The class of context-free languages is closed under
union,
concatenation,
Kleene star,
reversal.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 39 / 40
Closure Properties for CFLs
The class of context-free languages is not closed under intersection!
Hence it is not closed under complement either (why?)
Consider these two CFLs:
C = {ambncn | m, n ∈ N}
D = {anbncm | m, n ∈ N}
Exercise: Prove that they are context-free!
But C ∩ D is the language B = {anbncn | n ∈ N} which we just
showed is not context-free.
However, we do have: If A is context-free and R is regular then
A ∩ R is context-free.
Models of Computation (Sem 2, 2021) Pushdown Automata © University of Melbourne 40 / 40