Pushdown Automata

PDAs

Costas Busch - LSU 1

 Pushdown Automaton -- PDA
Input String

Stack

States

Costas Busch - LSU 2

 Initial Stack Symbol

Stack Stack

stack
$ z top
head

bottom special symbol

Appears at time 0
Costas Busch - LSU 3
 The States

Input Pop Push

symbol symbol symbol

q1 a, b c q2

Costas Busch - LSU 4

 q1 a, b c q
2

input
! a ! ! a !

stack
b top c
h Replace h
e e
$ Costas Busch - LSU
$ 5
 q1 a, e c q
2

input
! a ! ! a !

stack c
b top b
h Push h
e e
$ Costas Busch - LSU
$ 6
 q1 a, b e q
2

input
! a ! ! a !

stack
b top
h Pop h
e e
$ Costas Busch - LSU
$ 7
 q1
a, e e q
2

input
! a ! ! a !

stack
b top b
h No Change h
e e
$ Costas Busch - LSU
$ 8
 Non-Determinism
PDAs are non-deterministic
Allowed non-deterministic transitions

a, b c q2

q1 q1 e,b c q
2

e - transition
a, b c q3
Costas Busch - LSU 9
 Example PDA

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

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 10
 L( M ) = {a b : n 0}
n n

Basic Idea:

1. Push the as 2. Match the bs on input

on the stack with as on stack

3. Match
found
a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 11
Execution Example: Time 0
Input
a a a b b b
$
Stack

current a, e a b, a e
state

q0 e , e e q b, a e q e , $ $ q3
1 2
Costas Busch - LSU 12
 Time 1
Input
a a a b b b
$
Stack

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 13
 Time 2
Input
a a a b b b a
$
Stack

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 14
 Time 3
Input a
a a a b b b a
$
Stack

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 15
 Time 4
a
Input
a
a a a b b b a
$
Stack

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 16
 Time 5
a
Input
a
a a a b b b a
$
Stack

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 17
 Time 6
Input a
a a a b b b a
$
Stack

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 18
 Time 7
Input
a a a b b b a
$
Stack

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 19
 Time 8
Input
a a a b b b
$
Stack

a, e a b, a e
accept

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 20
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
Costas Busch - LSU 21
Rejection Example: Time 0
Input
a a b
$
Stack

current a, e a b, a e
state

q0 e , e e q b, a e q e , $ $ q3
1 2
Costas Busch - LSU 22
Rejection Example: Time 1
Input
a a b
$
Stack

current a, e a b, a e
state

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 23
Rejection Example: Time 2
Input
a a b a
$
Stack

current a, e a b, a e
state

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 24
Rejection Example: Time 3
Input a
a a b a
$
Stack

current a, e a b, a e
state

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 25
Rejection Example: Time 4
Input a
a a b a
$
Stack

current a, e a b, a e
state

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 26
Rejection Example: Time 4
Input a
a a b a
$
Stack
reject
current a, e a b, a e
state

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 27
There is no accepting computation for aab
The string aab is rejected by the PDA

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 28
 Another PDA example

*
PDA M: L( M ) = {vv : v {a, b} } R

a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 29
 *
Basic Idea: L( M ) = {vv : v {a, b} }R

1. Push v 3. Match v R on input

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

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 30
Execution Example: Time 0
Input
a b b a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 31
 Time 1
Input
a b b a
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 32
 Time 2
Input
b
a b b a
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 33
 Time 3
Input
b
a b b a
Guess the middle a
of string $
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 34
 Time 4
Input
b
a b b a
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 35
 Time 5
Input
a b b a
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 36
 Time 6
Input
a b b a
$
Stack
a, e a a, a e
b, e b b, b e
accept

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 37
Rejection Example: Time 0
Input
a b b b
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 38
 Time 1
Input
a b b b
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 39
 Time 2
Input
b
a b b b
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 40
 Time 3
Input
b
a b b b
Guess the middle a
of string $
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 41
 Time 4
Input
b
a b b b
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 42
 Time 5
Input There is no possible transition.

a b b b Input is not a
consumed
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 43
Another computation on same string:
Input Time 0
a b b b
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 44
 Time 1
Input
a b b b
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 45
 Time 2
Input
b
a b b b
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 46
 Time 3
Input b
b
a b b b
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 47
 Time 4 b
Input b
b
a b b b
a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 48
 Time 5 b
Input b
No accept state b
a b b b is reached a
$
Stack
a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 49
 There is no computation
that accepts string abbb

abbb L(M )

a, e a a, a e
b, e b b, b e

q0 e,e e q1 e,$ $ q2
Costas Busch - LSU 50
 Pushing & Popping Strings

Input Pop Push

symbol string string

a , w1 w2
q1 q2

Costas Busch - LSU 51

Example:
a , eb cdf
q1 q2

input
L a L L a L

stack
top c push
e top d
pop string
b f
string h Replace h
e e
$ $
Costas Busch - LSU 52
 a , eb cdf
q1 q2

Equivalent
transitions
pop
a, e e e, b e
q1
e, e e push
e, e f e, e d e, e c q2

Costas Busch - LSU 53

 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 e b, 0 e

q1 e, $ $ q2
Costas Busch - LSU 54
Execution Example: Time 0
Input
a b b b a a

$
a, $ 0$ b, $ 1$
Stack
a, 0 00 b, 1 11
a, 1 e b, 0 e
current
state e, $ $
q1 q2
Costas Busch - LSU 55
 Time 1
Input
a b b b a a
0
$
a, $ 0$ b, $ 1$ Stack
a, 0 00 b, 1 11
a, 1 e b, 0 e

q1 e, $ $ q2
Costas Busch - LSU 56
 Time 3
Input
a b b b a a
0
$
a, $ 0$ b, $ 1$ Stack
a, 0 00 b, 1 11
a, 1 e b, 0 e

q1 e, $ $ q2
Costas Busch - LSU 57
 Time 4
Input
a b b b a a
1
$
a, $ 0$ b, $ 1$ Stack
a, 0 00 b, 1 11
a, 1 e b, 0 e

q1 e, $ $ q2
Costas Busch - LSU 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 e b, 0 e

q1 e, $ $ q2
Costas Busch - LSU 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 e b, 0 e

q1 e, $ $ q2
Costas Busch - LSU 60
 Time 7
Input
a b b b a a
1
$
a, $ 0$ b, $ 1$ Stack
a, 0 00 b, 1 11
a, 1 e b, 0 e

q1 e, $ $ q2
Costas Busch - LSU 61
 Time 8
Input
a b b b a a

$
a, $ 0$ b, $ 1$
Stack
a, 0 00 b, 1 11
a, 1 e b, 0 e
accept
q1 e, $ $ q2
Costas Busch - LSU 62
Formalities for PDAs

Costas Busch - LSU 63

 a , w1 w2
q1 q2

Transition function:

d (q1 , a ,w1 ) = {(q2,w2 )}

Costas Busch - LSU 64

 a , w1 w2 q2

q1

a , w1 w3 q3

Transition function:

d (q1 , a ,w1 ) = {(q2,w2 ), (q3,w3 )}

Costas Busch - LSU 65

 Formal Definition
Pushdown Automaton (PDA)

M = (Q, , , , q0 , z, F ) Accept
states
States

Input Stack
alphabet Transition Initial start
Stack
function state symbol
alphabet
Costas Busch - LSU 66
 Instantaneous Description

( q, u , s )

Current Current
state Remaining stack
input
contents

Costas Busch - LSU 67

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

q0 e,e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 68
Example: Instantaneous Description
(q2 , bb, aa$)
a
Time 5: Input a
a a a b b b a
$
Stack
a, e a b, a e

q0 e,e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 69
We write:

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

Time 4 Time 5

Costas Busch - LSU 70

A computation:

(q0 , aaabbb,$) ! (q1 , aaabbb,$) !

(q1 , aabbb, a$) ! (q1 , abbb, aa$) ! (q1 , bbb, aaa$) !
(q2 , bb, aa $) ! (q2 , b, a$) ! (q2 , e ,$) ! (q3 , e ,$)

a, e a b, a e

q0 e , e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 71
(q0 , aaabbb,$) ! (q1 , aaabbb,$) !
(q1 , aabbb, a$) ! (q1 , abbb, aa$) ! (q1 , bbb, aaa$) !
(q2 , bb, aa $) ! (q2 , b, a$) ! (q2 , e ,$) ! (q3 , e ,$)

For convenience we write:

*
(q0 , aaabbb,$) ! (q3 , e ,$)

Costas Busch - LSU 72

 Language of PDA

Language L(M ) accepted by PDA M :

*
L( M ) = {w : (q0 , w, z ) ! (q f , e , s)}

Initial state Accept state

Costas Busch - LSU 73

Example: *
(q0 , aaabbb,$) ! (q3 , e ,$)

aaabbb L(M )

PDA M :

a, e a b, a e

q0 e,e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 74
 *
(q0 , a b ,$) ! (q3 , e ,$)
n n

n n
a b L(M )
PDA M :

a, e a b, a e

q0 e,e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 75
 Therefore: n n
L( M ) = {a b : n 0}

PDA M :

a, e a b, a e

q0 e,e e q1 b, a e q2 e , $ $ q3
Costas Busch - LSU 76