Pushdown Automata

PDAs

1
 Context-Free Languages

Context-Free Pushdown
Grammars Automata

stack

automaton

2
 Pushdown Automaton -- PDA
Input String

Stack

States

3
 Initial Stack Symbol

Stack Stack

stack
$ z top
head

bottom
special symbol
4
 The States

Input Pop Push

symbol symbol symbol

a, b → c
q1 q2

Alternatively
a,b / c
q1 q2
5
 a, b → c
q1 q2

input
 a   a 

stack
b top c
h Replace h
e e
$ $
6
 a,  → c
q1 q2

input
 a   a 

stack c
b top b
h Push h
e e
$ $
7
 a, b → 
q1 q2

input
 a   a 

stack
b top
h Pop h
e e
$ $
8
 a,  → 
q1 q2

input
 a   a 

stack
b top b
h No Change h
e e
$ $
9
 A Possible Transition

a, $ → 
q1 q2
input
 a   a 

stack empty
$ top Pop

10
 A Bad Transition

a, b → c
q1 q2
input
 a 

Empty stack
HALT

The automaton Halts in state q1

and Rejects the input string
11
 A Bad Transition

a,  → c
q1 q2
input
 a 

Empty stack
HALT

The automaton Halts in state q1

and Rejects the input string
12
No transition is allowed to be followed
When the stack is empty

x, y → z
q1 q2

Empty stack

13
 A Good Transition

a, $ → b
q1 q2
input
 a   a 

stack
$ top Pop b

14
 Non-Determinism

a, b → c q2

q1 , b → c
q1 q2

a, b → c  − transition
q3

These are allowed transitions in a

Non-deterministic PDA (NPDA)
15
 NPDA: Non-Deterministic PDA

Example:

a,  → a b, a → 

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

current a,  → a b, a → 
state
 ,  →  q b, a →  q , $ → $ q
q0 1 2 3
17
 Time 1
Input
a a a b b b
$
Stack

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
18
 Time 2
Input
a a a b b b a
$
Stack

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
19
 Time 3
Input a
a a a b b b a
$
Stack

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
20
 Time 4
a
Input
a
a a a b b b a
$
Stack

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
21
 Time 5
a
Input
a
a a a b b b a
$
Stack

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
22
 Time 6
Input a
a a a b b b a
$
Stack

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
23
 Time 7
Input
a a a b b b a
$
Stack

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
24
 Time 8
Input
a a a b b b
$
Stack

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

All the input is consumed

AND
The last state is a final state

At the end of the computation,

we do not care about the stack contents

26
 The input string aaabbb
is accepted by the NPDA:

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
27
In general,

L = {a b : n  0}
n n

is the language accepted by the NPDA:

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
28
 Another NPDA example

NPDA M

L( M ) = {ww } R

a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
29
Execution Example: Time 0
Input
a b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
30
 Time 1
Input
a b b a a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
31
 Time 2
Input
b
a b b a a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
32
 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
33
 Time 4
Input
b
a b b a a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
34
 Time 5
Input
a b b a a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
35
 Time 6
Input
a b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 
accept
q0 ,  →  q1 , $ → $ q2
36
Rejection Example: Time 0
Input
a b b b
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
37
 Time 1
Input
a b b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
38
 Time 2
Input
b
a b b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
39
 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
40
 Time 4
Input
b
a b b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
41
 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
42
Another computation on same string:
Input Time 0
a b b b
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
43
 Time 1
Input
a b b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
44
 Time 2
Input
b
a b b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
45
 Time 3
Input b
b
a b b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
46
 Time 4 b
Input b
b
a b b b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
47
 Time 5 b
Input b
No final state b
a b b b is reached a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
48
 There is no computation
that accepts string abbb

abbb  L(M )

a,  → a a, a → 
b,  → b b, b → 

q0 ,  →  q1 , $ → $ q2
49
A string is rejected if there is
no computation such that:

All the input is consumed

AND
The last state is a final state

At the end of the computation,

we do not care about the stack contents

50
In other words, a string is rejected
if in every computation with this string:

The input cannot be consumed

OR
The input is consumed and the last
state is not a final state
OR
The stack head moves below the
bottom of the stack

51
 Pushing Strings

Input Pop Push

symbol symbol string

a, b → w
q1 q2

52
Example:
a, b → cdf
q1 q2

input
a a

c pushed
stack d
top string
b f
h Push h
e e
$ $
53
 Another NPDA example
NPDA M
L( M ) = {w : na = nb }

a, $ → 0$ b, $ → 1$
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 

q1 , $ → $ q2
54
Execution Example: Time 0
Input
a b b a a b

$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 
current
state
q1 , $ → $ q2
55
 Time 1
Input
a b b a a b
0
$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 

q1 , $ → $ q2
56
 Time 3
Input
a b b b a a
0
$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 

q1 , $ → $ q2
57
 Time 4
Input
a b b b a a
1
$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 

q1 , $ → $ q2
58
 Time 5
Input
a b b b a a 1
1
$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 

q1 , $ → $ q2
59
 Time 6
Input
a b b b a a 1
1
$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 

q1 , $ → $ q2
60
 Time 7
Input
a b b b a a
1
$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 

q1 , $ → $ q2
61
 Time 8
Input
a b b b a a

$
a, $ → 0$ b, $ → 1$
Stack
a, 0 → 00 b, 1 → 11
a, 1 →  b, 0 → 
accept
q1 , $ → $ q2
62
Formalities for NPDAs

63
 a, b → w
q1 q2

Transition function:

 (q1, a, b) = {( q2 , w)}

64
 a, b → w q2

q1

a, b → w q3

Transition function:

 (q1, a, b) = {( q2 , w), (q3 , w)}

65
 Formal Definition
Non-Deterministic Pushdown Automaton
NPDA
M = (Q, Σ, Γ, δ, q0 , z , F ) Final
States states

Input Stack
alphabet Transition Initial start
Stack
function state symbol
alphabet
66
 Instantaneous Description

( q, u , s )

Current Current
state Remaining stack
input
contents

67
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
68
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
69
We write:

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

Time 4 Time 5

70
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
71
(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 ,  ,$)

72
 Formal Definition

Language L(M ) of NPDA M :


L( M ) = {w : (q0 , w, s )  (q f ,  , s ' )}

Initial state Final state

73
Example: 
(q0 , aaabbb,$)  (q3 ,  ,$)

aaabbb  L(M )

NPDA M :

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
74
 
(q0 , a b ,$)  (q3 ,  ,$)
n n

a b  L(M )
n n

NPDA M :

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
75
 Therefore: L( M ) = {a b : n  0}
n n

NPDA M :

a,  → a b, a → 

q0  ,  →  q1 b, a →  q2  , $ → $ q3
76
 Problems
# 4:
Design a NPDA to accept the following Language :

L(M) = { anb2n , n ≥ 0 }

77
 Time - 0
Input String

a a b b b b

$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q2 q3 q4

78
 Time - 1
Input String

a a b b b b

$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q2 q3 q4

79
 Time - 2
Input String

a a b b b b

0
0
$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q2 q3 q4

80
 Time - 3
Input String

a a b b b b 0
0
0
0
$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q2 q3 q4

81
 Time - 4
Input String

a a b b b b 0
0
0
0
$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q2 q3 q4

82
 Time - 5
Input String

a a b b b b
0
0
0
$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q2 q3 q4

83
 Time - 6
Input String

a a b b b b

0
0
$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q2 q3 q4

84
 Time - 7
Input String

a a b b b b

$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q q q4
2 3

85
 Time - 8
Input String

a a b b b b

“Accept”

$
a, → 00 b,0 → 
Stack

, →  b,0 →  ,$ →$

q1 q q q4
2 3

86
 Problems
# 5:
Design a NPDA to accept the following Language :

L(M) = { wcwR, w{a,b}* }

87
 L(M) = { wcwR, w{a,b}* }

a,  → a a, a → 
b,  → b b, b → 

q0 c, →  q1 , $ → $ q2
88
Execution Example: Time 0
Input
a b c b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 c, →  q1 , $ → $ q2
89
 Time 1
Input
a b c b a
a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 c, →  q1 , $ → $ q2
90
 Time 2
Input
b
a b c b a
a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 c, →  q1 , $ → $ q2
91
 Time 3
Input
b
a b c b a
a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 c, →  q1 , $ → $ q2
92
 Time 4
Input
b
a b c b a
a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 c, →  q1 , $ → $ q2
93
 Time 5
Input
a b c b a
a
$
Stack
a,  → a a, a → 
b,  → b b, b → 

q0 c, →  , $ → $ q2
q1
94
 Time 6
Input
a b c b a
$
Stack
a,  → a a, a → 
b,  → b b, b → 
accept
q0 c, →  q1 , $ → $ q2
95
 Problems
# 6:
Design a NPDA to accept the following Language :

L(M) = { anbmcn+m , n 0, m0 }

96
 L(M) = { anbmcn+m , n 0, m0 }

a,$ → 0$
a,0 → 00 b,1 → 11

b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 97
Input String

a a b c c c

a,$ → 0$
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 98
Input String

a a b c c c

a,$ → 0$ 0
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 99
Input String

a a b c c c

0
a,$ → 0$ 0
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 100
Input String

a a b c c c
1
0
a,$ → 0$ 0
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 101
Input String

a a b c c c
1
0
a,$ → 0$ 0
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 102
Input String

a a b c c c

0
a,$ → 0$ 0
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 103
Input String

a a b c c c

a,$ → 0$ 0
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1
2 3

c,1 → 
q c,0 → 
4 104
Input String

a a b c c c

a,$ → 0$ 0
a,0 → 00 b,1 → 11 $
Stack
b,$ → 1$
b,0 → 10 q5
, →  q q
q1 accept
2 3

c,1 → 
q c,0 → 
4 105