Pushdown Automata (PDA)

Chapter 6

1
Topics
• Pushdown Automata
• PDAs accepting by final state and empty stack
• Equivalence of PDAs and CFGs
• Deterministic PDAs

2
PDA - the automata for CFLs
• PDA =[  -NFA + “a stack” ]
• Why a stack?

Input -NFA Accept/reject

string

A stack filled with “stack symbols”

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

4
 δ : The Transition Function
old state input symb. Stack top new state(s) new Stack top(s)
δ : Q x ∑ x  => Q x 
δ(q,a,X) = {(p,Y), …}
1. state transition from q to p
a X Y
2. a is the next input symbol q p
3. X is the current stack top symbol
4. Y is the replacement for X;
it is in * (a string of stack symbols) Y=? Action
i. Set Y =  for: Pop(X) i) Y= Pop(X)
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 the iii) Y=Z1Z2..Zk Pop(X)
new stack top) Push(Zk)
Push(Zk-1)
…
Push(Z2)
Push(Z1)

5
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

6
Example
Let Lwwr = {wwR | w is in (0+1)*}
• CFG for Lwwr : S==> 0S0 | 1S1 | 
• PDA for Lwwr :
P := ( Q,∑, , δ,q0,Z0,F )

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

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

8
PDA for Lwwr
1. δ(q0,0, Z0)={(q0,0Z0)} Initial state of the PDA:
2. δ(q0,1, Z0)={(q0,1Z0)}

3. δ(q0,0, 0)={(q0,00)} Stack q0

4. δ(q0,0, 1)={(q0,01)} top
Z0
5. δ(q0,1, 0)={(q0,10)}
6. δ(q0,1, 1)={(q0,11)}

7. δ(q0, , 0)={(q1, 0)}

8. δ(q0, , 1)={(q1, 1)}
9. δ(q0, , Z0)={(q1, Z0)}

10. δ(q1,0, 0)={(q1, )}

11. δ(q1,1, 1)={(q1, )}

12. δ(q1, , Z0)={(q2, Z0)}

9
Example 2: Language of balanced
parenthesis
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 symbol
(, ( / ( (
popping mode
(, Z0 / ( Z0

To allow adjacent
10
blocks of nested paranthesis
Example 2: Language of balanced
parenthesis (another design)
∑ = { (, ) }
(,Z0 / ( Z0 G= {Z0, ( }
(,( / ( ( Q = {q0,q1}
), ( / 

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

11
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
12
How does the PDA for Lwwr work on input “1111”?

(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 13
(q2, ,Z0)
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:
• {w | (q0,w,Z0) |---* (q,, A) }, s.t., q  F

• 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.

14
Example: L of balanced
parenthesis

An equivalent PDA that

PDA that accepts by final state accepts by empty stack
(,Z0 / ( Z0
PF: PN: (, ( / ( (
(,Z0 / ( Z0
(,( / ( ( ), ( / 
), ( /  ,Z0 / 

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

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

16
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 simulating PN

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

PN

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

17
Example: Matching parenthesis “(” “)”
PN: ( {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) }
δN(q0,),Z1) = { (q0, ) } δf(q0,(,Z1) = { (q0, Z1Z1) }
δ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

18
PF==> PN Construction

Whenever PF reaches a final state, just make an  -

transition into a new end state, clear out the stack and
accept

PN:
, X0/Z0X0 , any/  , any/ 
New , any/ 
start p0 q0 pe
…
, any/ 
PF

PN = (Q U {p0,pe}, ∑,  U {X0}, δN, p0, X0)

19
Equivalence of PDAs and CFGs

PDA by PDA by
≡
final state empty stack

?
CFG

20
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
PDA

OUTPUT
INPUT

w (acceptance by
empty stack)
reject

implements

CFG

21
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 a
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 the stack top has a terminal symbol, and if it matches with the
next symbol in the input string, then pop it

22
 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:

A
For all A  V : 
δ(q,  ,A) = { (q, ) | “A ==>”  P}
…

…
Before: After:
a…
a For all a  T: a pop
δ(q,a,a)= { (q,  ) }
…

…
23
Example: CFG to PDA

• G = ( {S,A}, {0,1}, P, S) 1,1 / 

0,0 / 

• P: ,A / 01
,A / A1

• S ==> AS |  ,A / 0A1

,S / 
• A ==> 0A1 | A1 | 01 ,S / AS
,S / S
• PDA = ({q}, {0,1}, {0,1,A,S}, δ, q, S) q

• δ:
• δ(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
24
 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 / 
=> 0011
δ(q, 1, 1) = { (q,  ) } ,S / AS
,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

25
Converting a PDA into a CFG

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:
• [qZqk] => a[pY1q1] [q1Y2q2] [q2Y3q3]… [qk-1Ykqk]

26
Example: Bracket matching
• To avoid confusion, we will use b=“(“ and e=“)”

PN: ( {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. δ(q0,  ,Z0) = { (q0,  ) }
4. [q0Z0q0] => 

Let A=[q0Z0q0]
If you were to directly write a CFG: Simplifying,
Let B=[q0Z1q0]
S => b S e S |  0. S => A 0. S => b B S | 
1. A => b B A 1. B => b B B | e
2. B => b B B
3. B => e
4. A => 

27
Deterministic PDA: Definition

A PDA is deterministic if and only if:

1. δ(q,a,X) has at most one member for any a  ∑ U {}.
2. If δ(q,a,X) is non-empty for some a∑, then δ(q, ,X) must be
empty.

28
 Initial state of the PDA:

PDA for Lwwr Stack q0

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

3. δ(q0,0, 0)={(q0,00)} Grow the stack by pushing new symbols on

4. δ(q0,0, 1)={(q0,01)} top of old(w-part)
5. δ(q0,1, 0)={(q0,10)}
6. δ(q0,1, 1)={(q0,11)}

Switch to popping mode, nondeterministically

7. δ(q0, , 0)={(q1, 0)}
(boundary between w and wR)
8. δ(q0, , 1)={(q1, 1)}
9. δ(q0, , Z0)={(q1, Z0)}
Shrink the stack by popping matching
10. δ(q1,0, 0)={(q1, )} symbols (wR-part)
11. δ(q1,1, 1)={(q1, )}
Enter acceptance state
29
12. δ(q1, , Z0)={(q2, Z0)}
This PDA for Lwwr is non-
deterministic
Grow stack
0, Z0/0Z0
Why
Whydoes
doesitithave
haveto
to
1, Z0/1Z0 Pop stack for be
benon-
non-
0, 0/00 matching symbols deterministic?
deterministic?
0, 1/01
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
removeguessing,
guessing,
popping mode impose
imposethe theuser
userto
to
insert
insertccininthe
the
middle
middle
30
D-PDA for Lwcwr = {wcwR | c is some
special symbol not in w}
Note:
Note:
••all
alltransitions
transitionshave
have
Grow stack become
0, Z0/0Z0
Pop stack for becomedeterministic
deterministic
1, Z0/1Z0 matching symbols
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

31
PDA vs DPDA vs Regular
languages

Lwcwr Lwwr

Regular languages D-PDA

non-deterministic PDA

32
END

33