Pushdown Automata (PDA)

Reading: Chapter 6

1
PDA - the automata for CFLs
 What is?
 FA to Reg Lang, PDA is to CFL
 PDA == [  -NFA + “a stack” ]
 Why a stack?

Input -NFA Accept/reject

string

A stack filled with “stack symbols”

2
Pushdown Automata -
Definition
 A PDA P := ( Q,∑,, δ,q0,Z0,F ):
 Q: states of the -NFA
 ∑: input alphabet
 : stack symbols
 δ: transition function
 q0: start state
 Z0: Initial stack top symbol
 F: Final/accepting states

3
 old state input symb. Stack top new state(s) new Stack top(s)

δ : Q x ∑ x  => Q x 

δ : The Transition Function

δ(q,a,X) = {(p,Y), …}
1. state transition from q to p
2. a is the next input symbol a X Y
ddee nn--

3. X is the current stack top symbol q p

NNoo
t

Y is the replacement for X;

t
eer

4.
r

it is in * (a string of stack
m

Y=? Action
m

symbols)
in
in
i

Set Y =  for: Pop(X) i) Y= Pop(X)

ssm
i

i.
m

ii. If Y=X: stack top is unchanged

ii) Y=X Pop(X)
iii. If Y=Z1Z2…Zk: X is Push(X)
popped and is replaced by Y
in reverse order (i.e., Z1 will be iii) Y=Z1Z2..Zk Pop(X)
the new stack top) Push(Zk)
Push(Zk-1)
…
Push(Z2)
Push(Z1)

4
Example
Let Lwwr = {wwR | w is in (0+1)*}
 CFG for L
wwr : S==> 0S0 | 1S1 | 
 PDA for L
wwr :
 P := ( Q,∑, , δ,q ,Z ,F )
0 0

= ( {q0, q1, q2},{0,1},{0,1,Z0},δ,q0,Z0,{q2})

5
 Initial state of the PDA:

Stack q0
PDA for Lwwr top Z0

1. δ(q0,0, Z0)={(q0,0Z0)}
First symbol push on stack
2. δ(q0,1, Z0)={(q0,1Z0)}

3. δ(q0,0, 0)={(q0,00)}
4. δ(q0,0, 1)={(q0,01)}
Grow the stack by pushing
5. δ(q0,1, 0)={(q0,10)}
new symbols on top of old
6. δ(q0,1, 1)={(q0,11)} (w-part)
7. δ(q0, , 0)={(q1, 0)}
Switch to popping mode, nondeterministically
8. δ(q0, , 1)={(q1, 1)}
(boundary between w and wR)
9. δ(q0, , Z0)={(q1, Z0)}

10. δ(q1,0, 0)={(q1, )} Shrink the stack by popping matching

11. δ(q1,1, 1)={(q1, )} symbols (wR-part)

Enter acceptance state

12. δ(q1, , Z0)={(q2, Z0)}
6
 PDA as a state diagram
δ(qi,a, X)={(qj,Y)}

Next Current Stack

input stack Top
Current symbol top Replacement
state (w/ string Y)

a, X / Y Next
qi qj state

7
 PDA for Lwwr: Transition Diagram

Grow stack ∑ = {0, 1}

0, Z0/0Z0 G = {Z0, 0, 1}
1, Z0/1Z0 Pop stack for
Q = {q0,q1,q2}
0, 0/00 matching symbols
0, 1/01
1, 0/10 0, 0/ 
1, 1/11 1, 1/ 

q0 q1 q2
, Z0/Z0
, Z0/Z0 , Z0/Z0
, 0/0
, 1/1 Go to acceptance
Switch to
popping mode

This would be a non-deterministic PDA 8

 Example 2: language of
balanced paranthesis
Pop stack for ∑ = { (, ) }
matching symbols G = {Z0, ( }
Grow stack
Q = {q0,q1,q2}
(, Z0 / ( Z0
(, ( / ( ( ), ( / 

q0 q1 q2
, Z0 / Z0 ), ( /  , Z0 / Z0
, Z0 / Z0 Go to acceptance (by final state)
Switch to when you see the stack bottom symbo
(, ( / ( (
popping mode
(, Z0 / ( Z0

To allow adjacent
blocks of nested paranthesis 9
0n1n grammar

10
 L = {wcw^R}
 a,b
 abcba
 aaabcbaaa
 L= {accepting equal nos of a and b}

11
Example 2: language of balanced
paranthesis (another design)
∑ = { (, ) }
(,Z0 / ( Z0 G = {Z0, ( }
(,( / ( (
), ( / 
Q = {q0,q1}

start ,Z0/ Z0
q0 q1
,Z0/ Z0

12
PDA’s Instantaneous
Description (ID)
A PDA has a configuration at any given instance:
(q,w,y)
 q - current state
 w - remainder of the input (i.e., unconsumed part)
 y - current stack contents as a string from top to bottom
of stack
If δ(q,a, X)={(p, A)} is a transition, then the following are also true:
 (q, a, X ) |--- (p,,A)

 (q, aw, XB ) |--- (p,w,AB)

|--- sign is called a “turnstile notation” and represents

one move
|---* sign represents a sequence of moves
13
How does the PDA for Lwwr
work on input “1111”?
All moves made by the non-deterministic PDA
(q0,1111,Z0)

(q1,1111,Z0) Path dies…

(q0,111,1Z0)

(q0,11,11Z0) (q1,111,1Z0) Path dies…

(q0,1,111Z0) (q1,11,11Z0)

(q0,,1111Z0) (q1,1,111Z0) (q1,1,1Z0) Acceptance by

final state:

(q1, ,1111Z0) (q1, ,11Z0) (q1, ,Z0) = empty input

Path dies… AND
Path dies… final state
(q2, ,Z0)
14
There are two types of PDAs that one can design:
those that accept by final state or by empty stack

Acceptance by…
 PDAs that accept by final state:
 For a PDA P, the language accepted by P, denoted
by L(P) by final state, is: Checklist:

{w | (q0,w,Z0) |---* (q,, A) }, s.t., q  F - input exhausted?
- in a final state?

 PDAs that accept by empty stack:

 For a PDA P, the language accepted by P, denoted
by N(P) by empty stack, is:

{w | (q0,w,Z0) |---* (q, , ) }, for any q  Q.
Q) Does a PDA that accepts by empty stack Checklist:
- input exhausted?
need any final state specified in the design?
- is the stack empty? 16
 Example: L of balanced
parenthesis
An equivalent PDA that
PDA that accepts by final state accepts by empty stack
(,Z0 / ( Z0
PF: (,Z0 / ( Z0
PN: (, ( / ( (
(,( / ( ( ), ( / 
), ( /  ,Z0 / 

,Z0/ Z0 start
start
q0 q1 q0
,Z0/ Z0 ,Z0/ Z0

How will these two PDAs work on the input: ( ( ( ) ) ( ) ) ( )

17
PDAs accepting by final state and empty
stack are equivalent
 PF <= PDA accepting by final state

PF = (QF,∑, , δF,q0,Z0,F)
 PN <= PDA accepting by empty stack

PN = (QN,∑, , δN,q0,Z0)
 Theorem:

(PN==> PF) For every PN, there exists a PF s.t. L(PF)=L(PN)


(PF==> PN) For every PF, there exists a PN s.t. L(PF)=L(PN)

19
How to convert an empty stack PDA into a final state PDA?

PN==> PF construction
 Whenever PN’s stack becomes empty, make PF go to
a final state without consuming any addition symbol
 To detect empty stack in PN: PF pushes a new stack
symbol X0 (not in  of PN) initially before simultating
PN

PF: P N: , X0/ X0
, X0/Z0X0 , X0/ X0
New
start p0 q0 , X0/ X0 pf
…
, X0 / X0
, X0/ X0

PF = (QN U {p0,pf}, ∑, PN U {X0}, δF, p0, X0, {pf}) 20

 Example: Matching parenthesis “(” “)”
P N: ( {q0}, {(,)}, {Z0,Z1}, δN, q0, Z0 ) Pf: ( {p0,q0 ,pf}, {(,)}, {X0,Z0,Z1}, δf, p0, X0 , pf)

δN : δN(q0,(,Z0) = { (q0,Z1Z0) } δf : δf(p0, ,X0) = { (q0,Z0) }

δN(q0,(,Z1) = { (q0, Z1Z1) } δf(q0,(,Z0) = { (q0,Z1 Z0) }
δf(q0,(,Z1) = { (q0, Z1Z1) }
δN(q0,),Z1) = { (q0, ) }
δf(q0,),Z1) = { (q0, ) }
δN(q0, ,Z0) = { (q0, ) } δf(q0, ,Z0) = { (q0, ) }
δf(p0, ,X0) = { (pf, X0 ) }
(,Z0 /Z1Z0 (,Z0/Z1Z0
(,Z1 /Z1Z1 (,Z1/Z1Z1
),Z1 /  ),Z1/ 
,Z0 /   ,Z0/ 

start
q0
start
,X /Z X
0 0 0
,X / X
0 0
p0 q0 pf

Accept by empty stack Accept by final state 21

How to convert an final state PDA into an empty stack PDA?

PF==> PN construction
 Main idea:
 Whenever PF reaches a final state, just make an  -transition into a
new end state, clear out the stack and accept
 Danger: What if PF design is such that it clears the stack midway
without entering a final state?
 to address this, add a new start symbol X0 (not in  of
PF)
PN = (Q U {p0,pe}, ∑,  U {X0}, δN, p0, X0)
PN:
, X0/Z0X0 , any/  , any/ 
New
start p0 q0 , any/  pe
…
, any/ 
PF

22
Equivalence of PDAs and
CFGs

23
CFGs == PDAs ==> CFLs

PDA by PDA by
≡
final state empty stack

?
CFG

24
This is same as: “implementing a CFG using a PDA”

Converting CFG to PDA

Main idea: The PDA simulates the leftmost derivation on a given
w, and upon consuming it fully it either arrives at acceptance (by
empty stack) or non-acceptance.

accept

OUTPUT
PDA
INPUT

w (acceptance
by empty
stack) reject

implements

CFG

25
This is same as: “implementing a CFG using a PDA”

Converting a CFG into a PDA

Main idea: The PDA simulates the leftmost derivation on a given w,
and upon consuming it fully it either arrives at acceptance (by
empty stack) or non-acceptance.
Steps:
1. Push the right hand side of the production onto the stack,
with leftmost symbol at the stack top
2. If stack top is the leftmost variable, then replace it by all its
productions (each possible substitution will represent a
distinct path taken by the non-deterministic PDA)
3. If stack top has a terminal symbol, and if it matches with the
next symbol in the input string, then pop it
State is inconsequential (only one state is needed)

26
 Formal construction of PDA
from CFG Note: Initial stack symbol (S)
same as the start variable
in the grammar
 Given: G= (V,T,P,S)
 Output: PN = ({q}, T, V U T, δ, q, S)
 δ:
Before: After:
 For all A  V , add the following
A
transition(s) in the PDA: 
…

…

δ(q,  ,A) = { (q, ) | “A ==>”  P}
Before:  For all a  T, add the following After: a…
a transition(s) in the PDA: a pop
…

δ(q,a,a)= { (q,  ) }

…


27
Example: CFG to PDA
1,1 / 
 G = ( {S,A}, {0,1}, P, S) 0,0 / 
,A / 01
 P: ,A / A1
,A / 0A1
 S ==> AS |  ,S / 
,S / AS
 A ==> 0A1 | A1 | 01 ,S / S
q
 PDA = ({q}, {0,1}, {0,1,A,S}, δ, q, S)
 δ:
 δ(q,  , S) = { (q, AS), (q,  )}
 δ(q,  , A) = { (q,0A1), (q,A1), (q,01) }
 δ(q, 0, 0) = { (q,  ) }
 δ(q, 1, 1) = { (q,  ) } How will this new PDA work?
Lets simulate string 0011
28
 Simulating string 0011 on the
new PDA … Leftmost deriv.:
1,1 / 
0,0 / 
PDA (δ): ,A / 01
S => AS
δ(q,  , S) = { (q, AS), (q,  )} ,A / A1 => 0A1S
δ(q,  , A) = { (q,0A1), (q,A1), (q,01) } ,A / 0A1
=> 0011S
δ(q, 0, 0) = { (q,  ) } ,S / 
δ(q, 1, 1) = { (q,  ) } ,S / AS => 0011
,S / S
Stack moves (shows only the successful path): q

0 0
A A 1 1
A 1 1 1 1 1 Accept by
S S S S S S S S
empty stack
0 0 1 1 

S =>AS =>0A1S =>0011S => 0011

29
1.S → 0BB
2.B → 0S | 1S | 0

1.S → aSb
2.S → a | b | ε

30
 a(n)b(m)c(n)
 m,n>=1

 PDA
 CFG
 CFG->PDA
 PDA->CFG
 Example string: aabbbcc
31
Converting a PDA into a CFG
 Main idea: Reverse engineer the
productions from transitions
If δ(q,a,Z) => (p, Y1Y2Y3…Yk):
1. State is changed from q to p;
2. Terminal a is consumed;
3. Stack top symbol Z is popped and replaced with a
sequence of k variables.
 Action: Create a grammar variable called
“[qZp]” which includes the following
production:

[qZp] => a[pY1q1] [q1Y2q2] [q2Y3q3]… [qk-1Ykqk]

 Proof discussion (in the book) 33

 Example: Bracket matching
 To avoid confusion, we will use b=“(“ and e=“)”
P N: ( {q0}, {b,e}, {Z0,Z1}, δ, q0, Z0 )
0. S => [q0Z0q0]
1. δ(q0,b,Z0) = { (q0,Z1Z0) } 1. [q0Z0q0] => b [q0Z1q0] [q0Z0q0]
2. δ(q0,b,Z1) = { (q0,Z1Z1) } 2. [q0Z1q0] => b [q0Z1q0] [q0Z1q0]
3. [q0Z1q0] => e
3. δ(q0,e,Z1) = { (q0,  ) }
4. [q0Z0q0] => 
4. δ(q0,  ,Z0) = { (q0,  ) }
Let A=[q0Z0q0] Simplifying,
Let B=[q0Z1q0]
If you were to directly write a CFG: 0. S => b B S | 
0. S => A
1. A => b B A 1. B => b B B | e
S => b S e S |  2. B => b B B
3. B => e
4. A => 

34
 Two ways to build a CFG
Build a PDA Construct (indirect)
CFG from PDA

Derive CFG directly (direct)

Similarly… Two ways to build a PDA

Derive a CFG Construct
(indirect)
PDA from CFG

Design a PDA directly (direct)

35
Deterministic PDAs

36
 This PDA for Lwwr is non-deterministic

Grow stack Why

0, Z0/0Z0 Whydoes
doesitit
1, Z0/1Z0 Pop stack for have
haveto
tobe
be
0, 0/00 matching symbols non-
non-
0, 1/01 deterministic?
deterministic?
1, 0/10 0, 0/ 
1, 1/11 1, 1/ 

q0 q1 q2
, Z0/Z0 , Z0/Z0
, 0/0
, 1/1 Accepts by final state
Switch to To
Toremove
remove
popping mode guessing,
guessing,
impose
imposethetheuser
user
to
toinsert
insertccininthe
the
middle
middle 37
 Example shows that: Nondeterministic PDAs ≠ D-PDAs

D-PDA for Lwcwr = {wcwR | c is some

special symbol not in w}
Note:
Note:
•• all
alltransitions
transitions
Grow stack have
0, Z0/0Z0 Pop stack for havebecome
become
1, Z0/1Z0 matching symbols deterministic
deterministic
0, 0/00
0, 1/01 0, 0/ 
1, 0/10 1, 1/ 
1, 1/11

q0 q1 q2
c, Z0/Z0 , Z0/Z0
c, 0/0
c, 1/1 Accepts by
Switch to final state
popping mode

38
Deterministic PDA: Definition
 A PDA is deterministic if and only if:
1. δ(q,a,X) has at most one member for any
a  ∑ U {}

 If δ(q,a,X) is non-empty for some a∑,

then δ(q, ,X) must be empty.

39
PDA vs DPDA vs Regular
languages
Lwcwr Lwwr

Regular languages D-PDA

non-deterministic PDA

40
Summary
 PDAs for CFLs and CFGs
 Non-deterministic
 Deterministic
 PDA acceptance types
1. By final state
2. By empty stack
 PDA
 IDs, Transition diagram
 Equivalence of CFG and PDA
 CFG => PDA construction
 PDA => CFG construction
41