= 0} and {ww: w in {a,b}}. It demonstrates how a PDA accepts a string through its computations and rejects a string if it cannot consume all the input.">= 0} and {ww: w in {a,b}}. It demonstrates how a PDA accepts a string through its computations and rejects a string if it cannot consume all the input.">
Pushdown Automata Pdas
Pushdown Automata Pdas
Pushdown Automata Pdas
PDAs
stack
head
Stack
Stack
top
The States
Pop
symbol
Input
symbol
q1
a, b c
Push
symbol
q2
q1
a, b c
q2
input
stack
b
h
e
$
top
Replace
c
h
e
$
5
q1
a, c
q2
input
stack
b
h
e
$
top
Push
c
b
h
e
$
6
q1
a, b
q2
input
stack
b
h
e
$
top
Pop
h
e
$
7
q1
a,
q2
input
stack
b
h
e
$
top
No Change
b
h
e
$
8
Empty Stack
q1
input
stack
a, $
top
q2
Pop
empty
A Possible Transition
q1
input
stack
a, $ b
top
q2
Pop
10
Non-Determinism
PDAs are non-deterministic
Allowed non-deterministic transitions
a, b c
q2
q1
a, b c
q1
, b c
q2
transition
q3
11
Example PDA
PDA
L( M ) {a b : n 0}
n
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
12
L( M ) {a b : n 0}
n
Basic Idea:
1. Push the as
on the stack
a, a
b, a
3. Match
found
b,
a
,
$
$
q3
q0
q2
q1
13
a a a b b b
$
Stack
current
state
a, a
b, a
, q b, a q , $ $ q
q0
3
2
1
14
Time 1
Input
a a a b b b
$
Stack
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
15
Time 2
Input
a a a b b b
a
$
Stack
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
16
Time 3
Input
a
a
$
a a a b b b
Stack
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
17
Time 4
Input
a a a b b b
a
a
a
$
Stack
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
18
Time 5
Input
a a a b b b
a
a
a
$
Stack
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
19
Time 6
Input
a
a
$
a a a b b b
Stack
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
20
Time 7
Input
a
$
a a a b b b
Stack
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
21
Time 8
Input
a a a b b b
$
Stack
a, a
b, a
accept
b,
a
,
$
$
q3
q0
q2
q1
22
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
24
In general,
L {a b : n 0}
n n
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
25
Rejection Example:
Time 0
Input
a a b
$
Stack
current
state
a, a
b, a
, q b, a q , $ $ q
q0
3
2
1
26
Rejection Example:
Time 1
Input
a a b
$
Stack
current
state
a, a
b, a
b,
a
,
$
$
q3
q2
q1
q0
27
Rejection Example:
Time 2
Input
a a b
$
Stack
current
state
a, a
b, a
b,
a
,
$
$
q3
q2
q1
q0
28
Rejection Example:
Time 3
Input
a
a
a a b
$
Stack
current
state
a, a
b, a
b,
a
,
$
$
q3
q2
q1
q0
29
Rejection Example:
Time 4
Input
a
a
a a b
$
Stack
current
state
a, a
b, a
b,
a
,
$
$
q3
q2
q1
q0
30
Rejection Example:
Time 4
Input
a
a
a a b
reject
current
state
a, a
Stack
b, a
b,
a
,
$
$
q3
q2
q1
q0
31
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
32
L( M ) {vv : v {a, b} }
R
PDA
a, a
a, a
b, b
b, b
q0
q1
, $ $
q2
34
Basic Idea:
1. Push v
on stack
a, a
L( M ) {vv : v {a, b} }
3. Match v R on input
with v on stack
2. Guess
middle
of input
b, b
q0
a, a
b, b
q1
4. Match
found
, $ $
q2
35
Execution Example:
Time 0
Input
a b b a
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
36
Time 1
Input
a b b a
a
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
37
Time 2
Input
b
a
$
a b b a
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
38
Time 3
Input
a b b a
a, a
a, a
b, b
b, b
q0
q1
, $ $
b
a
$
Stack
q2
39
Time 4
Input
b
a
$
a b b a
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
40
Time 5
Input
a b b a
a
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
41
Time 6
Input
a b b a
$
a, a
a, a
b, b
b, b
Stack
accept
q0
q1
, $ $
q2
42
Rejection Example:
Time 0
Input
a b b b
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
43
Time 1
Input
a b b b
a
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
44
Time 2
Input
b
a
$
a b b b
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
45
Time 3
Input
a b b b
a, a
a, a
b, b
b, b
q0
q1
, $ $
b
a
$
Stack
q2
46
Time 4
Input
b
a
$
a b b b
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
47
Time 5
There is no possible transition.
Input
a b b b
Input is not
consumed
a, a
a, a
b, b
b, b
q0
q1
, $ $
a
$
Stack
q2
48
Input
Time 0
a b b b
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
49
Time 1
Input
a b b b
a
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
50
Time 2
Input
b
a
$
a b b b
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
51
Time 3
b
b
a
$
Input
a b b b
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
52
Time 4
b
b
b
a
$
Input
a b b b
a, a
a, a
b, b
b, b
q0
q1
, $ $
Stack
q2
53
Time 5
Input
a b b b
No final state
is reached
a, a
a, a
b, b
b, b
q0
q1
, $ $
b
b
b
a
$
Stack
q2
54
There is no computation
that accepts string abbb
abbb L(M )
a, a
a, a
b, b
b, b
q0
q1
, $ $
q2
55
PDA
M
q0
56
Execution Example:
Time 0
Input
a a b
a, a
b, a
b, $
Stack
q0
57
Time 1
Input
a a b
a, a
b, a
b, $
a
$
Stack
q0
58
Time 2
Input
a a b
a, a
b, a
b, $
a
a
$
Stack
q0
59
Time 3
Input
a a b
a
$
a, a
b, a
b, $
Stack
accept
q0
60
Rejection example:
Time 0
Input
a b b b
$
Stack
q0
61
Time 1
Input
a b b b
a, a
b, a
b, $
a
$
Stack
q0
62
Time 2
Input
a b b b
a, a
b, a
b, $
Stack
q0
63
Time 3
Input
a b b b
a, a
b, a
b, $
Stack
q0
64
Time 4
Input
a b b b
a, a
b, a
b, $
Stack
q0
65
Pushing Strings
Pop
symbol
Input
symbol
q1
a, b w
Push
string
q2
66
Example:
q1
a, b cdf
q2
input
stack
b
h
e
$
top
Push
c
d
f
h
e
$
pushed
string
67
L( M ) {w {a, b} : na ( w) nb ( w)}
*
PDA
a, $ 0$
a, 0 00
a, 1
b, $ 1$
b, 1 11
b, 0
q1
, $ $
q2
68
Execution Example:
Time 0
Input
a b
b b a a
a, $ 0$
a, 0 00
a, 1
current
state
b, $ 1$
b, 1 11
b, 0
q1
, $ $
$
Stack
q2
69
Time 1
Input
a b
b b
a, $ 0$
a, 0 00
a, 1
a a
b, $ 1$
b, 1 11
b, 0
q1
, $ $
0
$
Stack
q2
70
Time 3
Input
a b
b b a a
a, $ 0$
a, 0 00
a, 1
b, $ 1$
b, 1 11
b, 0
q1
, $ $
0
$
Stack
q2
71
Time 4
Input
a b
b b a a
a, $ 0$
a, 0 00
a, 1
b, $ 1$
b, 1 11
b, 0
q1
, $ $
1
$
Stack
q2
72
Time 5
Input
a b
b b a a
a, $ 0$
a, 0 00
a, 1
b, $ 1$
b, 1 11
b, 0
q1
, $ $
1
1
$
Stack
q2
73
Time 6
Input
a b
b b a a
a, $ 0$
a, 0 00
a, 1
b, $ 1$
b, 1 11
b, 0
q1
, $ $
1
1
$
Stack
q2
74
Time 7
Input
a b
b b a a
a, $ 0$
a, 0 00
a, 1
b, $ 1$
b, 1 11
b, 0
q1
, $ $
1
$
Stack
q2
75
Time 8
Input
a b
b b a a
a, $ 0$
a, 0 00
a, 1
b, $ 1$
b, 1 11
b, 0
q1
, $ $
$
Stack
accept
q2
76
77
q1
a, b w
q2
Transition function:
a, b w
q2
q1
a, b w
q3
Transition function:
Formal Definition
Pushdown Automaton (PDA)
M (Q, , , , q0 , z, F )
States
Input
alphabet
Transition Initial
Stack
function
state
alphabet
Final
states
Stack
start
symbol
80
Instantaneous Description
( q, u , s )
Current
state
Remaining
input
Current
stack
contents
81
Example:
Instantaneous Description
Input
a a a b b b
a, a
b, a
a
a
a
$
Stack
b,
a
,
$
$
q3
q0
q2
q1
82
Example:
Instantaneous Description
Input
a a a b b b
a, a
b, a
a
a
a
$
Stack
b,
a
,
$
$
q3
q0
q2
q1
83
We write:
Time 5
84
A computation:
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
85
Formal Definition
Language
L(M )
of PDA M :
L( M ) {w : (q0 , w, s ) (q f , , s ' )}
Initial state
Final state
87
Example:
PDA M :
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
88
a b L(M )
n n
PDA M :
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
89
Therefore:
L( M ) {a b : n 0}
n n
PDA M :
a, a
b, a
b,
a
,
$
$
q3
q0
q2
q1
90