Pushdown Automata

PDAs

Fall 2005 Costas Busch - RPI 1

 Pushdown Automaton -- PDA
Input String

Stack

States

Fall 2005 Costas Busch - RPI 2

 Initial Stack Symbol

Stack Stack

stack
$ z top
head

bottom special symbol

Appears at time 0
Fall 2005 Costas Busch - RPI 3
 The States

Input Pop Push

symbol symbol symbol

a, b  c
q1 q2

Fall 2005 Costas Busch - RPI 4

 a, b  c
q1 q2

input
 a   a 

stack
b top c
h Replace h
e e
$ $
Fall 2005 Costas Busch - RPI 5
 a,   c
q1 q2

input
 a   a 

stack c
b top b
h Push h
e e
$ $
Fall 2005 Costas Busch - RPI 6
 a, b  
q1 q2

input
 a   a 

stack
b top
h Pop h
e e
$ $
Fall 2005 Costas Busch - RPI 7
 a,   
q1 q2

input
 a   a 

stack
b top b
h No Change h
e e
$ $
Fall 2005 Costas Busch - RPI 8
 Empty Stack
a, $  
q1 q2
input
 a   a 
stack empty
$ top Pop

When the stack gets empty,

the automaton HALTS
(no more transitions after q2)
Fall 2005 Costas Busch - RPI 9
 A Possible Transition

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

stack
$ top Pop b

Fall 2005 Costas Busch - RPI 10

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

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

a, b  c
  transition
q3
Fall 2005 Costas Busch - RPI 11
 Example PDA

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

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 12
 L( M )  {a b : n  0}
n n

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
Fall 2005 Costas Busch - RPI 13
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
Fall 2005 Costas Busch - RPI 14
 Time 1
Input
a a a b b b
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 15
 Time 2
Input
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 16
 Time 3
Input a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 17
 Time 4
a
Input
a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 18
 Time 5
a
Input
a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 19
 Time 6
Input a
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 20
 Time 7
Input
a a a b b b a
$
Stack

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 21
 Time 8
Input
a a a b b b
$
Stack

a,   a b, a  
accept
q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 22
 A string is accepted if there is
a computation such that:

All the input is consumed

AND
The last state is an accepting state

At the end of the computation,

we do not care about the stack contents
(the stack can be empty at the last state)
Fall 2005 Costas Busch - RPI 23
 The input string aaabbb
is accepted by the PDA:

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 24
 In general,
n n
L  {a b : n  0}

is the language accepted by the PDA:

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 25
Rejection Example: Time 0
Input
a a b
$
Stack

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

q0  ,    q b, a   q  , $  $ q
1 2 3
Fall 2005 Costas Busch - RPI 26
Rejection Example: Time 1
Input
a a b
$
Stack

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

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 27
Rejection Example: Time 2
Input
a
a a b
$
Stack

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

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 28
Rejection Example: Time 3
Input a
a
a a b
$
Stack

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

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 29
Rejection Example: Time 4
Input a
a
a a b
$
Stack

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

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 30
Rejection Example: Time 4
Input a
a
a a b
$
Stack
reject
current a,   a b, a  
state

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 31
 The input string aab
is rejected by the PDA:

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 32
 A string is rejected if there is
no computation such that:

All the input is consumed

AND
The last state is an accept state

At the end of the computation,

we do not care about the stack contents
Fall 2005 Costas Busch - RPI 33
 Another PDA example

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

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

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 34
 
Basic Idea: L( M )  {vv : v  {a, b} }
R

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
Fall 2005 Costas Busch - RPI 35
Execution Example: Time 0
Input
a b b a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 36
 Time 1
Input
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 37
 Time 2
Input
b
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 38
 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
Fall 2005 Costas Busch - RPI 39
 Time 4
Input
b
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 40
 Time 5
Input
a b b a
a
$
Stack
a,   a a, a  
b,   b b, b  

,    , $  $ q2
q0 q1
Fall 2005 Costas Busch - RPI 41
 Time 6
Input
a b b a
$
Stack
a,   a a, a  
b,   b b, b  
accept
q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 42
Rejection Example: Time 0
Input
a b b b
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 43
 Time 1
Input
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 44
 Time 2
Input
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 45
 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
Fall 2005 Costas Busch - RPI 46
 Time 4
Input
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 47
 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  

,    , $  $ q2
q0 q1
Fall 2005 Costas Busch - RPI 48
Another computation on same string:
Input Time 0
a b b b
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 49
 Time 1
Input
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 50
 Time 2
Input
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 51
 Time 3
Input b
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 52
 Time 4 b
Input b
b
a b b b
a
$
Stack
a,   a a, a  
b,   b b, b  

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 53
 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
Fall 2005 Costas Busch - RPI 54
 There is no computation
that accepts string abbb

abbb  L(M )

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

q0 ,    q1 , $  $ q2
Fall 2005 Costas Busch - RPI 55
 Another PDA example

*
L( M )  {w {a, b} : in every prefix v, na (v)  nb (v)  1}

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

PDA M
q0
Fall 2005 Costas Busch - RPI 56
Execution Example: Time 0
Input
a a b

a,   a $
b, a   Stack
b, $  

q0
Fall 2005 Costas Busch - RPI 57
 Time 1
Input
a a b a
a,   a $
b, a   Stack
b, $  

q0
Fall 2005 Costas Busch - RPI 58
 Time 2
Input
a
a a b a
a,   a $
b, a   Stack
b, $  

q0
Fall 2005 Costas Busch - RPI 59
 Time 3
Input
a a b a
a,   a $
b, a   Stack
b, $  

accept
q0
Fall 2005 Costas Busch - RPI 60
Rejection example: Time 0
Input
a b b b

a,   a $
b, a   Stack
b, $  

q0
Fall 2005 Costas Busch - RPI 61
 Time 1
Input
a b b b a
a,   a $
b, a   Stack
b, $  

q0
Fall 2005 Costas Busch - RPI 62
 Time 2
Input
a b b b

a,   a $
b, a   Stack
b, $  

q0
Fall 2005 Costas Busch - RPI 63
 Time 3
Input
a b b b

a,   a
b, a   Stack
b, $  

q0
Fall 2005 Costas Busch - RPI 64
 Time 4
Input
a b b b

a,   a
b, a   Stack
b, $  

Halt and Reject

q0
Fall 2005 Costas Busch - RPI 65
 Pushing Strings

Input Pop Push

symbol symbol string

a, b  w
q1 q2

Fall 2005 Costas Busch - RPI 66

Example:
a, b  cdf
q1 q2

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

c pushed
stack d
top string
b f
h Push h
e e
$ $
Fall 2005 Costas Busch - RPI 67
 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
Fall 2005 Costas Busch - RPI 68
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
Fall 2005 Costas Busch - RPI 69
 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
Fall 2005 Costas Busch - RPI 70
 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
Fall 2005 Costas Busch - RPI 71
 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
Fall 2005 Costas Busch - RPI 72
 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
Fall 2005 Costas Busch - RPI 73
 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
Fall 2005 Costas Busch - RPI 74
 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
Fall 2005 Costas Busch - RPI 75
 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
Fall 2005 Costas Busch - RPI 76
 Formalities for PDAs

Fall 2005 Costas Busch - RPI 77

 a, b  w
q1 q2

Transition function:

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

Fall 2005 Costas Busch - RPI 78

 q2
a, b  w

q1

a, b  w q3

Transition function:

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

Fall 2005 Costas Busch - RPI 79
 Formal Definition
Pushdown Automaton (PDA)

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

Input Stack
alphabet Transition Initial start
Stack
function state symbol
alphabet
Fall 2005 Costas Busch - RPI 80
 Instantaneous Description

( q, u , s )

Current Current
Remaining
state stack
input
contents

Fall 2005 Costas Busch - RPI 81

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
Fall 2005 Costas Busch - RPI 82
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
Fall 2005 Costas Busch - RPI 83
 We write:

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

Time 4 Time 5

Fall 2005 Costas Busch - RPI 84

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
Fall 2005 Costas Busch - RPI 85
(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 ,  ,$)

Fall 2005 Costas Busch - RPI 86

 Formal Definition

Language L(M ) accepted by PDA M :

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

Initial state Accept state

Fall 2005 Costas Busch - RPI 87

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

aaabbb  L(M )

PDA M :

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 88
 
n n
(q0 , a b ,$)  (q3 ,  ,$)

n n
a b  L(M )

PDA M :

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 89
 n n
Therefore: L( M )  {a b : n  0}

PDA M :

a,   a b, a  

q0  ,    q1 b, a   q2  , $  $ q3
Fall 2005 Costas Busch - RPI 90