Chapter 7
Pushdown Automata
Regular Languages (Review)
Regular languages are
described by regular expressions.
generated via regular grammars.
accepted by
deterministic finite automata DFA
nondeterministic finite automata NFA
There is an equivalence between the deterministic and
nondeterministic versions
Every regular language RL is CFL
But some CFL are not regular:
L = {anbn : n 1} has CFG
S aSb | ab
The language {wwR : w {a, b}*} has CFG
S aSa | bSb | e
Context-Free Languages (Review)
CFL are generated by a context-free grammar CFG
A grammar G = (NT, T, S, P) is CFG if all
production rules have the form
A → y, where A NT, and y (NT T)*
i.e., there is a single NT on the left hand side.
A language L is CFL iff there is a CFG G such that
L = L(G)
All regular languages, and some non-regular
languages, can be generated by CFGs
regular languages are a proper subset of
context-free languages.
Stack Memory
The language L = {wcwR : w {a, b}*} is CFL but
not RL
We can not have a DFA for L
Problem is memory, DFA’s cannot remember
left hand substring
What kind of memory do we need to be able to
recognize strings in L?
Answer: a stack
Stack Memory
Example: u = aaabbcbbaaa L
We push the first part of the string onto the
stack and
after the c is encountered
start popping characters off of the stack and
matching them with each character.
if everything matches, this string L
Stack Memory
We can also use a stack for counting out equal
numbers of a’s and b’s.
Example:
L = {anbn : n ≥ 0}
w = aaaabbbb L
Push the a’s onto the stack, then pop an a off
and match it with each b.
If we finish processing the string successfully
(and there are no more a’s on our stack), then
the string belongs to L.
7.1: Nondeterministic Push-Down
Automata (1)
A language is context free (CFL) iff some
Nondeterministic PushDown Automata (NPDA)
recognizes (accepts) it.
Intuition: NPDA = NFA + one stack for memory.
Stack remembers info about previous part of string
E.g., to accept anbn
Deterministic PushDown Automata (DPDA) can
accept some but not all of the CFLs
Thus, there is no longer an equivalence between the
deterministic and nondeterministic versions,
i.e., languages recognized by DPDA are a
proper subset of context-free languages.
7.1: NPDA (2)
You can only access the top element of the stack.
To access the top element of the stack, you have to pop it
off the stack.
Once the top element of the stack has been popped, if
you want to save it, you need to push it back onto the
stack.
Symbols from the input string must be read one symbol at a
time. You cannot back up.
The current configuration (state, string, stack) of the NPDA
includes:
The current state
the remaining symbols left in the input string, and
the entire contents of the stack
7.1: NPDA (3)
NPDA consists of
Input file, Control unit, Stack
Output
output is yes/no
indicates string belongs to given language
Each move
reads a symbol from the input
e-moves are legal
pops a symbol from the stack
no move is possible if stack is empty
pushes a string, right-to-left, onto the stack
move to the target state
7.1: NPDA (4)
A NPDA is a seven-tuple M = (Q, Σ, Γ, d, q0, z, F)
where
Q finite set of states
S finite set of input alphabet
G finite set of stack alphabet
d transition function from
Q (S {e}) G finite subsets of Q × Γ*
d(qn, a, A) = {(qm, B)}
q0 start state q0 Q
z initial stack symbol zΓ
F final states FQ
7.1: NPDA (5)
There are three things in a NPDA:
Stack
State
An input tape
q0
tape head
z Scan from left to right
7.1: NPDA (6)
The transition function deserves further explanation
δ : Q × (Σ {e}) × Γ → finite subsets of Q × Γ*
A 3-tuple mapped onto one or more 2-tuples
Transition function now depends upon three items:
current state, input symbol, and stack symbol
7.1: NPDA (7)
Note that in a DFA, each transition told us that
when we were in a given state and saw a specific
symbol, we moved to a specified state.
In a NPDA, we read an input symbol, but we also
need to know what is on the stack before we can
decide what new state to move to.
When moving to the new state, we also need to
decide what to do with the stack.
7.1: NPDA (8)
What it does mean if d(qn, a, A) = (qm, B) ?
It means if
the current state is qn
the current input letter is a
the top of the stack is A
Then the machine should
change the state to qm
process input letter a
pop A off the stack a, A/B
push B onto the stack
qn qm
7.1: NPDA (9)
What it does mean if d(qn, a, A) = (qm, e) ?
It means if
the current state is qn
the current input letter is a
the top of the stack is A
Then the machine should
change the state to qm
process input letter a a, A/e
qn qm
pop A off the stack
don’t push anything onto the stack
7.1: NPDA (10)
What it does mean if d(qn, a, A) = (qm, BA) ?
change the state to qm
process input letter a
don’t pop anything from the stack
push B onto the stack
a, A/BA
qn qm
7.1: NPDA (11)
What it does mean if d(qn, e, A) = (qm, B) ?
change the state to qm
don’t process any input letter
pop A from the stack
push B onto the stack
e, A/B
qn qm
7.1: NPDA (12)
What it does mean if d(qn, a, A) = (qm, A) ?
change the state to qm
process input letter a
don’t pop anything from the stack
don’t push anything onto the stack
a, A/A
qn qm
7.1: NPDA (13)
popped pushed
Language: L = {anbn : n ≥ 0} input
M = (Q, Σ, Γ, δ, q0, Z, F), where
Q = {q0, q1, q2, q3} δ(q0, a, Z) = {(q1, aZ)}
δ(q0, e, Z) = {(q3, e)}
Σ = {a, b}
δ(q1, a, a) = {(q1, aa)}
Γ = {Z, a}
δ(q1, b, a) = {(q2, e)}
δ δ(q2, b, a) = {(q2, e)}
q0 is the start state δ(q2, e, Z) = {(q3, e)}
Z is the initial stack symbol
F = {q3}
Can be modeled with graph
edge triplet is (input, popped, pushed)
7.1: NPDA (14)
Language: L = {anbn : n ≥ 0}
M = (Q, Σ, Γ, δ, q0, Z, F), where
popped
input
pushed
7.1: NPDA (15)
A NPDA configuration is represented by
[qn, u, a] where
qn : current state
u : unprocessed input
a : current stack content
if d(qn, a, A) = (qm, B) then [qn, au, Aa]├ [qm, u, Ba]
The notation [qn, u, a] ├ [qm, v, b] indicates that
configuration [qm, v, b] is obtained from [qn, u, a] by
a single transition of the NPDA
7.1: NPDA (16)
The notation [qn, u, a] ├* [qm, v, b] indicates that
configuration [qm, v, b] is obtained from [qn, u, a]
by zero or more transitions of the NPDA
A computation of a NPDA is a sequence of
transitions beginning with start state.
7.1: PDA (17)
The language accepted by NPDA M is
L(M) = {w S* :
Accept when out of input at a final state
[q0, w, z] ├* [qi, e, u] with qi F
Accept when out of input at an empty stack
[q0, w, z] ├* [qi, e, e] qi may not be in F
Accept when out of input at a final state and empty
stack
[q0, w, z] ├* [qi, e, e] with qi F
7.1: NPDA (18)
Language: L = {anbn : n ≥ 0}
The computation generated by the input string
aaabbb is
[q0, aaabbb, Z] ├ [q1, aabbb, aZ] ├ [q1, abbb, aaZ] ├
[q1, bbb, aaaZ] ├ [q2, bb, aaZ] ├ [q2, b, aZ] ├
[q2, e, Z] ├ [q3, e, e]
Actions of the Example PDA
aaabbb
q0
Z
Actions of the Example PDA
aabbb
q1
a
Z
Actions of the Example PDA
abbb
q1
a
a
Z
Actions of the Example PDA
bbb
q1
a
a
a
Z
Actions of the Example PDA
bb
q2
a
a
Z
Actions of the Example PDA
q2
a
Z
Actions of the Example PDA
q2
Z
Actions of the Example PDA
q3
e
7.1: PDA (19)
L={wcwR | w{a,b}*} is CFL and accepted by NPDA
{Q={q0,q1,q2},S={a,b,c},q0,G={A,B,Z},Z,F={q2}}
d(q0, a, Z) = (q0, AZ) d(q0, c, Z) = (q1, Z)
d(q0, a, A) = (q0, AA) d(q0, c, A) = (q1, A)
d(q0, c, B) = (q1, B)
d(q0, a, B) = (q0, AB) d(q1, a, A) = (q1, e)
d(q0, b, Z) = (q0, BZ) d(q1, b, B) = (q1, e)
d(q0, b, A) = (q0, BA) d(q1, e, Z) = (q2, Z)
d(q0, b, B) = (q0, BB)
C, Z;Z
7.1: PDA (20)
The computation generated by the input string abcba
is
[q0, abcba, Z]
├ [q0, bcba, AZ]
├ [q0, cba, BAZ]
├ [q1, ba, BAZ]
├ [q1, a, AZ]
├ [q1, e, Z] C, Z;Z
├ [q2, e, Z]
7.1: PDA (21)
Consider w = aabcaaa
[q0, aabcaaa, Z]
├ [q0, abcaaa, AZ]
├ [q0, bcaaa, AAZ]
├ [q0, caaa, BAAZ]
├ [q1, aaa, BAAZ]
C, Z;Z
dead configuration, w = aabcaaa L
See Examples 7.4, 7.5
7.1: NPDA (22)
A deterministic pushdown accepter (which we have not yet
considered) must have only one transition for any given
input symbol and stack symbol.
A nondeterministic pushdown accepter may have no
transition or several transitions defined for a particular input
symbol and stack symbol.
In a npda, there may be several “paths” to follow to process
a given input string. Some of the paths may result in
accepting the string. Other paths may end in a non-
accepting state.
As with a nfa, a npda magically (and correctly) “guesses”
which path to follow through the machine in order to accept
a string (if the string is in the language).
7.1: NPDA (23)
must be e
7.1: NPDA (24)
7.1: NPDA (25)
7.2: PDA & CFL (1)
Every CFL is accepted by PDA
For any CFL L, there exists a PDA M such that
L(M) = L
The reverse is true as well
Let G be the CFG of L such that L(G) = L
Construct a PDA M such that L(M) = L(G) = L
M is constructed from CFG G
CFG PDA
7.2: PDA & CFL (2)
A context-free grammar is in Greibach Normal
Form (GNF) if every production is of the form
A → aX
where A NT, X NT*, and a Σ , i.e., A is a
Examples:
G1 = ({S,A}, {a,b}, S, {S→aSA | a, A→aA | b})
GNF
G2 = ({S,A},{a,b}, S, {S→AS|AAS, A→SA|aa})
not GNF
7.2: PDA & CFL (3)
Given a context-free grammar in GNF, the basic
idea is to construct a npda that does a leftmost
derivation of any string in the language.
Rules:
always have e-production from start state to
push S onto the stack.
push NTs on the right hand side onto the stack
the single terminal on the right hand side is
treated as input
NT on the left hand side is the top of the stack
to be popped
have e-production to accepting state if Z on top
of stack
7.2: PDA & CFL (4)
Always start with δ(q0, e, Z) = (q1, SZ)
begin in state q0, pop Z, move to q1 without
reading input, push SZ
Repeatedly apply rule
If A → aX add δ(q1, a, A) = (q1, X)
note always start and end in state q1
begin in state q1, pop A, move to state q1 while
reading input a, push X
Always end with δ(q1, e, Z) = (qf, e)
note Z must be at top of stack
begin in state q1, pop Z, move to state qf without
reading input sybol
7.2: PDA & CFL (5)
Input Grammar in Greibach NF G = (NT, S, P, S)
Output NPDA M = (Q, S, G, d, q0, Z, F)
Q = {q0, q1, qf}, S = S, G = NT {Z}, F = {qf}
d:
δ(q0, e, Z) = (q1, SZ) //always
d(q1, a, A) = (q1, w) if A → aw P
δ(q1, e, Z) = (qf, e) //always
7.2: PDA & CFL (6)
Simple example:
CFG G = ({S,A},{a,b}, S, {S→aSA|a,A→aA|b})
production transition
(always) δ(q0, e, Z) = {(q1, SZ)}
S → aSA | ae δ(q1, a, S) = {(q1, SA), (q1, e)}
A → aA δ(q1, a, A) = {(q1, A)}
A → be δ(q1, b, A) = {(q1, e)}
(always) δ(q1, e, Z) = {(qf, e)}
7.2: PDA & CFL (7)
7.2: PDA & CFL (8)
7.2: PDA & CFL (9)
Input CFG G = {{S, A, B}, {a, b}, S, P}
P:
S → aAB | aB
A → aAB | aB
B→b
What is NPDA? What is L(G)?
a, S/AB
a, S/B
e, Z/SZ
q0 q1 b, B/e
e, Z/e
a, A/AB
a, A/B qf
7.2: PDA & CFL (10)
Computation of aaabbb
[q0, aaabbb, Z]
├ [q1, aaabbb, SZ]
S aAB ├ [q1, aabbb, ABZ]
aaABB ├ [q1, abbb, ABBZ]
aaaBBB ├ [q1, bbb, BBBZ]
aaabBB ├ [q1, bb, BBZ]
aaabbB ├ [q1, b, BZ]
aaabbb ├ [q1, e, Z]
├ [qf, e, e]
On your own, draw computation trees for other strings not in the
language and see that they are not accepted.
7.2: PDA & CFL (11)
Let CFG G = ({S, A, B}, {a, b}, S, P) where P is
S aAA A aB | bB | a Bc
Construct NPDA M:
({q0, q1 , qf}, {a, b}, {S, A, B, Z}, d, q0, {qf})
where
d(q0, e, Z) = (q1, SZ)
d(q1, a, S) = (q1, AA) S aAA
d(q1, a, A) = {(q1, B), (q1, e)} A aB | ae
d(q1, b, A) = (q1, B) A bB
d(q1, c, B) = (q1, e) B ce
d(q1, e, Z) = (qf, e)
7.3: Deterministic PDA (1)
A PDA is deterministic if its transition function
satisfies both of the following properties
For all q Q, a S {e}, and X G,
the set d(q, a, X) has at most one element
there is only one move for any input and stack
combination
For all q Q and X G,
if d(q, e, X) {}, then d(q, a, X) = {} a S
an e-transition has no input-consuming alternatives,
i.e., there cannot exist another move with stack = X
from the same state q.
7.3: Deterministic PDA (2)
A language L is a deterministic context-free language if and only if
there is a DPDA that accepts L.
Some context-free languages which are initially described in a
nondeterministic way via a NPDA can also be described in a
deterministic way via DPDA.
Some context-free languages are inherently nondeterministic, e.g., L =
{w (a|b)* : w = wR} cannot be accepted by any dpda.
Deterministic PDA (DPDA) can only represent a subset of CFL, e.g., L
= {wwR | w (a|b)*} cannot be represented by DPDA
A key point in all this is that the equivalence between deterministic and
nondeterministic finite automata is not found with deterministic and
nondeterministic pushdown automata.
Unless otherwise stated, we assume that a PDA is nondeterministic
7.3: Deterministic PDA (3)
L = {an | n 0} {anbn | n 0} is CFL and accepted by a non-
deterministic PDA M
Q = {q0, q1, q2}, S = {a, b}, G = {Z, A}, q0, Z, F = {q2}
d(q0, a, Z) = (q0, AZ), d(q0, b, A) = (q1, e)
d(q0, e, Z) = (q2, e) d(q1, b, A) = (q1, e)
d(q0, e, Z) = (q2, e) d(q1, e, Z) = (q1, e)
d(q2, e, Z) = (q2, e) d(q2, e, A) = (q2, e)
d(q0, a, A) = (q0, AA)
a, A/AA
a, Z/AZ b, A/e
b, A/e
q0 q1
e, Z/e e, Z/e
e, A/e
q2
e, Z/e
7.3: Deterministic PDA (4)
The language of (strings over {a, b} of even length and
spelled the same forwards and backwards) = {wwR |
w {a, b}*} is CFL and accepted by a non-
deterministic PDA M
e, Z;Z
e, a;a
e, b;b
7.3: Deterministic PDA (5)
7.3: Deterministic PDA (6)
7.3: Deterministic PDA (7)
7.3: Deterministic PDA (8)
7.3: Deterministic PDA (9)
