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 FQ
 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 Bc

 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)