CHAPTER FIVE

PUSHDOWN AUTOMATON (PDA)

It is a way of implementing a CFG in a similar way we
design , DFA, for RE.
A DFA can remember a finite amount of information but,
PDA can remember an infinite amount of information.
PDA = FA + stack
PDA is a nondeterministic finite state automaton (NFA)
that permits ε-transitions and a stack.

1
 Formal Definition
Pushdown Automaton (PDA)

M (Q, Σ, Γ, δ, q0 , z , F ) Accept
states
States

Input Stack
alphabet Transition Initial start
Stack
function state symbol
alphabet
2
 Pushdown Automaton (PDA)
P Q , , ,  ( qi , a, m )  ( qk , n ),..., q0 ,  0 , F 
Q: A finite set of states.
 : A finite set of input symbols.
: A finite stack alphabet.
: The transition function with input:
qi is a state in Q.
a is a symbol in  or a =  (the empty string).
m is a stack symbol, m  
and the output is a finite set of pairs:
qk the new state.
n is the string of stack symbols that replaces m at the
top of the stack. If n = , then the stack is popped.
q0: The start state.
0 : Initially, the PDA’s stack consists this symbol and
nothing else.
F : The set of accepting states. 3
Pushdown Automaton -- PDA
Input String

Stack

States

4
 Initial Stack Symbol

Stack Stack

stack
$ z top
head

bottomspecial symbol
Appears at time 0
5
 The States

Input Pop Push

symbol symbol symbol

q1 a, b  c q2

6
 a, b  c
q1 q2

input
 a   a 

stack
b top c
h Replace h
e e
$ $
7
 a,   c
q1 q2

input
 a   a 

stack c
b top b
h Push h
e e
$ $
8
 a, b  
q1 q2

input
 a   a 

stack
b top
h Pop h
e e
$ $
9
 a,   
q1 q2

input
 a   a 

stack
b top b
h No Change h
e e
$ $
10
 Pop from Empty Stack
a, b  c
q1 q2
input
 a 
stack Pop Automaton halts!

top

If the automaton attempts to pop from

empty stack then it halts and rejects input

11
PDAs are non-deterministic
Allowed non-deterministic transitions

q2
a, b  c
, b  c
q1 q1 q2

a, b  c
  transition
q3
12
 Example PDA

n n
PDA M: L( M ) {a b : n 0}

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
13
 n n
L( M ) {a b : n 0}
Basic Idea:

Push the a’s 2. Match the b’s on input

on the stack with a’s on stack

3. Match
a,   a b, a   found

q0  ,    q1 b, a   q2  , $  $ q3
14
Execution Example: Time 0
Input
a a a b b b
$
Stack

current a,   a b, a  
state

q0  ,    q b, a   q  , $  $ q
1 2 3
15
 Time 1
Input
a a a b b b
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
16
 Time 2
Input
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
17
 Time 3
Input a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
18
 Time 4
a
Input
a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
19
 Time 5
a
Input
a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
20
 Time 6
Input a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
21
 Time 7
Input
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
22
 Time 8
Input
a a a b b b
$
Stack

a,   a b, a  
accept
q0  ,    q1 b, a   q2  , $  $ q3
23
A string is accepted if there is a computation such
that:

All the input is consumed

AND
The last state is an accepting state

24
Rejection Example: Time 0
Input
a a b
$
Stack

current a,   a b, a  
state

q0  ,    q b, a   q  , $  $ q
1 2 3
25
Rejection Example: Time 1
Input
a a b
$
Stack

current a,   a b, a  
state

q0  ,    q1 b, a   q2  , $  $ q3
26
Rejection Example: Time 2
Input
a
a a b
$
Stack

current a,   a b, a  
state

q0  ,    q1 b, a   q2  , $  $ q3
27
Rejection Example: Time 3
Input a
a
a a b
$
Stack

current a,   a b, a  
state

q0  ,    q1 b, a   q2  , $  $ q3
28
Rejection Example: Time 4
Input a
a
a a b
$
Stack

current a,   a b, a  
state

q0  ,    q1 b, a   q2  , $  $ q3
29
Rejection Example: Time 4
Input a
a
a a b
$
Stack
reject
current a,   a b, a  
state

q0  ,    q1 b, a   q2  , $  $ q3
30
There is no accepting computation foraab

The string aab is rejected by the PDA

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
31
 Another PDA example

R 
PDA M: L( M ) {vv : v  {a, b} }

a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
32
 R 
Basic Idea: L( M ) {vv : v  {a, b} }

Push v 3. Match v R on input

2. Guess
on stack with v on stack
middle
of input
a,   a a, a   4. Match
b,   b b, b   found

q0 ,    q1 , $  $ q2
33
Execution Example: Time 0
Input
a b b a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
34
 Time 1
Input
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
35
 Time 2
Input
b
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
36
 Time 3
Input
b
a b b a
Guess the middle a
of string $
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
37
 Time 4
Input
b
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
38
 Time 5
Input
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
39
 Time 6
Input
a b b a
$
Stack
a,   a a, a  
b,   b b, b  
accept
q0 ,    q1 , $  $ q2
40
Rejection Example: Time 0
Input
a b b b
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
41
 Time 1
Input
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
42
 Time 2
Input
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
43
 Time 3
Input
b
a b b b
Guess the middle a
of string $
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
44
 Time 4
Input
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
45
 Time 5
Input There is no possible
transition.
a b b b Input is not a
consumed
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
46
Another computation on same string:
Input Time 0
a b b b
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
47
 Time 1
Input
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
48
 Time 2
Input
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
49
 Time 3
Input b
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
50
 Time 4 b
Input b
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
51
 Time 5 b
Input b
No accept state b
a b b b is reached a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
52
 There is no computation
that accepts string abbb

abbb  L(M )

a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
53
Pushing & Popping Strings

Input Pop Push

symbol string string

a, w1  w2
q1 q2

54
Example: a, eb  cdf
q1 q2

input

 a 
 
 a 


stack
top c push
e top d
pop string
b f
string h Replac h
e e e
$ $
55
 a, eb  cdf
q1 q2

Equivalent
transitions
pop
a, e   a, b  
q1
,   
push
a,   f a,   d a,   c q
2

56
Formalities for PDAs

57
 a, w1  w2
q1 q2

Transition function:
 (q1, a,w1)  {(q2,w2 )}

58
 a, w1  w2 q2

q1

a, w1  w3 q3

Transition function:

 (q1, a,w1)  {(q2,w2 ), (q3,w3 )}

59
 Instantaneous Description

( q, u , s )

Current Current
Remaining
state stack
input
contents

60
Example: Instantaneous Description
(q1, bbb, aaa$)
a
Time 4: Input a
a a a b b b a
$
Stack
a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
61
Example: Instantaneous Description
(q2 , bb, aa$)
a
Time 5: Input a
a a a b b b a
$
Stack
a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
62
We write:

(q1, bbb, aaa$)  (q2 , bb, aa$)

Time 4 Time 5

63
A computation:

(q0 , aaabbb,$) (q1, aaabbb,$) 

(q1, aabbb, a$) (q1, abbb, aa$) (q1, bbb, aaa$) 
(q2 , bb, aa$) (q2 , b, a$) (q2 ,  ,$) (q3 ,  ,$)

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
64
(q0 , aaabbb,$) (q1, aaabbb,$) 
(q1, aabbb, a$) (q1, abbb, aa$) (q1, bbb, aaa$) 
(q2 , bb, aa$) (q2 , b, a$) (q2 ,  ,$) (q3 ,  ,$)

For convenience we write:


(q0 , aaabbb,$)  (q3 ,  ,$)

65