Pushdown Automata

PDAs

1
 Basic Structure of PDA
A pushdown automaton is a way to implement a
context-free grammar in a similar way we design DFA
for a regular grammar. A DFA can remember a finite
amount of information, but a PDA can remember an
infinite amount of information.
Basically a pushdown automaton is −

"Finite state machine" + "a stack“

A pushdown automaton has three components −
 an input tape,
 a control unit, and
 a stack with infinite size.

The stack head scans the top symbol of the stack.

2
 Basic Structure of PDA
A stack does two operations −
Push − a new symbol is added at the top.
Pop − the top symbol is read and removed.
A PDA may or may not read an input symbol, but it has to read
the top of the stack in every transition.

3
 Basic Structure of PDA
A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0,
I, F) −
Q is the finite number of states
∑ is input alphabet
S is stack symbols
δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*
q0 is the initial state (q0 ∈ Q)
I is the initial stack top symbol (I ∈ S)
F is a set of accepting states (F ∈ Q)
The following diagram shows a transition in a PDA from a
state q1 to state q2, labeled as a , b → c

4
 Pushdown Automaton -- PDA
Input String

Stack

States

5
 Initial Stack Symbol

Stack Stack

stack
$ z top
head

bottom special symbol

Appears at time 0
6
 The States

Input Pop Push

symbol symbol symbol

q1 a, b  c q2

7
 Terminologies Related to PDA

Instantaneous Description
The instantaneous description (ID) of a
PDA is represented by a triplet (q, w, s)
where
• q is the state
• w is unconsumed input
• s is the stack contents

8
 Terminologies Related to PDA
Notation
The "turnstile" notation is used for connecting pairs of
ID's that represent one or many moves of a PDA. The
process of transition is denoted by the turnstile symbol
"⊢".

Consider a PDA (Q, ∑, S, δ, q0, I, F). A transition can be

mathematically represented by the following turnstile
notation
(p, aw, Tβ) ⊢ (q, w, αb)

This implies that while taking a transition from state p

to state q, the input symbol ‘a’ is consumed, and the
top of the stack ‘T’ is replaced by a new string ‘α’.
10
 a, b  c
q1 q2

input
 a   a 

stack
b top Replac
c
h e h
e e
$ $
11
 a,   c
q1 q2

input
 a   a 

stack c
b top Pus
b
h h h
e e
$ $
12
 a, b  
q1 q2

input
 a   a 

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

input
 a   a 

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

stack Pop Automaton halts!

top

f the automaton attempts to pop from

empty stack then it halts and rejects input

15
 Non-Determinism
PDAs are non-deterministic
Allowed non-deterministic transitions

a, b  c q2

, b  c
q1 q1 q2

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

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

a,   a b, a  
Push the on the stack
𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
17
 n n
L( M ) {a b : n 0}
Basic Idea:

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

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

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

on the stack with a’s on stack

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

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
19
Execution Example: Time 0
Input
a a a b b b

Stack

current a,   a b, a  
state
𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
20
 Time 1
Input
a a a b b b
$
Stack

a,   a b, a  

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
21
 Time 2
Input
a a a b b b a
$
Stack

a,   a b, a  

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
22
 Time 3
Input a
a a a b b b a
$
Stack

a,   a b, a  

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
23
 Time 4
a
Input
a
a a a b b b a
$
Stack

a,   a b, a  

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
24
 Time 5
a
Input
a
a a a b b b a
$
Stack

a,   a b, a  

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
25
 Time 6
Input a
a a a b b b a
$
Stack

a,   a b, a  

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
26
 Time 7
Input
a a a b b b a
$
Stack

a,   a b, a  

𝜆, 𝜆→$ b, a   𝜆, $→ 𝜆
q0 q1 q2 q3
27
 Time 8
Input
a a a b b b
$
Stack

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

All the input is consumed

AND
The last state is an accepting state

we do not care about the stack contents

at the end of the accepting computation
29
Rejection Example: Time 0
Input
a a b
$
Stack

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

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

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

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

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

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

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

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

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

q0  ,    q1 b, a   q2  , $  $ q3
35
 aab
There is no accepting computation for

The string aab is rejected by the PDA

a,   a b, a  

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

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

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

q0 ,    q1 , $  $ q2
37
 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
38
Execution Example: Time 0
Input
a b b a
$
Stack
a,   a a, a  
b,   b b, b  

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

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

q0 ,    q1 , $  $ q2
41
 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
42
 Time 4
Input
b
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

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

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

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

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

q0 ,    q1 , $  $ q2
48
 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
49
 Time 4
Input
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

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

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

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

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

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

q0 ,    q1 , $  $ q2
56
 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
57
 There is no computation
that accepts stringabbb

abbb  L(M )

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

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

Input Pop Push

symbol string string

a, w1  w2
q1 q2

59
Example: a, eb  cdf
q1 q2

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

stack
top c push
e top d
pop string
b f
string h Repla h
e ce e
$ $
60
 a, eb  cdf
q1 q2

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

61
 Another PDA example
*
L( M ) {w  {a, b} : na ( w) nb ( w)}
PDA M

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

q1 , $  $ q2
62
Execution Example:Time 0
Input
a b b b a a

$
a, $  0$ b, $  1$
Stack
a, 0  00 b, 1  11
a, 1   b, 0  
current
state
q1 , $  $ q2
63
 Time 1
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
64
 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
65
 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
66
 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
67
 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
68
 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
69
 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
70
Formalities for PDAs

71
 a, w1  w2
q1 q2

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

72
 a, w1  w2 q2

q1

a, w1  w3 q3

Transition function:

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

73
 Formal Definition
Pushdown Automaton (PDA)

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

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

( q, u , s )

Current Current
state Remaining stack
input contents

75
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
76
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
77
We write:

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

Time 4 Time 5

78
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
79
(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 ,  ,$)

80
 Language of PDA

Language L(M ) accepted by PDAM :


L(M )  {w : (q0 ,w, z )  (qf , , s )}

Initial state Accept state

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

aaabbb L(M )

PDA M :

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
82
 
n n
(q0 , a b ,$)  (q3 ,  ,$)

n n
a b  L(M )

PDA M :

a,   a b, a  

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

PDA M :

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
84