Pushdown Automata�PDAs
1
Pushdown Automaton -- PDA
2
Input String
Stack
States
3
Initial Stack Symbol
Stack
Stack
bottom
special symbol
stack
head
top
Appears at time 0
The States
4
Input
symbol
Pop
symbol
Push
symbol
5
top
input
stack
Replace
6
Push
top
input
stack
7
Pop
top
input
stack
8
No Change
top
input
stack
9
Pop
top
input
stack
Empty Stack
empty
The automaton HALTS
No possible transition after
10
Pop
top
input
stack
A Possible Transition
Non-Determinism
11
PDAs are non-deterministic
Allowed non-deterministic transitions
Example PDA
12
PDA
13
Basic Idea:
on the stack
2. Match the b’s on input
with a’s on stack
3. Match
found
14
Execution Example:
Input
current
state
Time 0
Stack
15
Input
Time 1
Stack
16
Input
Stack
Time 2
17
Input
Stack
Time 3
18
Input
Stack
Time 4
19
Input
Stack
Time 5
20
Input
Stack
Time 6
21
Input
Stack
Time 7
22
Input
Time 8
accept
Stack
23
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)
24
The input string
is accepted by the PDA:
25
is the language accepted by the PDA:
In general,
26
Rejection Example:
Input
current
state
Time 0
Stack
27
Rejection Example:
Input
current
state
Time 1
Stack
28
Rejection Example:
Input
current
state
Time 2
Stack
29
Rejection Example:
Input
current
state
Time 3
Stack
30
Rejection Example:
Input
current
state
Time 4
Stack
31
Rejection Example:
Input
current
state
Time 4
Stack
reject
32
The input string
is rejected by the PDA:
33
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
Another PDA example
34
PDA
35
Basic Idea:
on stack
2. Guess
middle
of input
3. Match on input
with v on stack
4. Match
found
36
Execution Example:
Input
Time 0
Stack
37
Input
Time 1
Stack
38
Input
Time 2
Stack
39
Input
Time 3
Stack
Guess the middle
of string
40
Input
Time 4
Stack
41
Input
Time 5
Stack
42
Input
Time 6
Stack
accept
43
Rejection Example:
Input
Time 0
Stack
44
Input
Time 1
Stack
45
Input
Time 2
Stack
46
Input
Time 3
Stack
Guess the middle
of string
47
Input
Time 4
Stack
48
Input
Time 5
Stack
There is no possible transition.
Input is not consumed
49
Another computation on same string:
Input
Time 0
Stack
50
Input
Time 1
Stack
51
Input
Time 2
Stack
52
Input
Time 3
Stack
53
Input
Time 4
Stack
54
Input
Time 5
Stack
No final state
is reached
55
There is no computation
that accepts string
Another PDA example
56
PDA
57
Execution Example:
Input
Time 0
Stack
58
Input
Time 1
Stack
59
Input
Time 2
Stack
60
Input
Time 3
Stack
accept
61
Rejection example:
Input
Time 0
Stack
62
Input
Time 1
Stack
63
Input
Time 2
Stack
64
Input
Time 3
Stack
65
Input
Time 4
Stack
Halt and Reject
Pushing Strings
66
Input
symbol
Pop
symbol
Push
string
67
top
input
stack
Push
pushed
string
Example:
Another PDA example
68
PDA
69
Time 0
Input
current
state
Stack
Execution Example:
70
Time 1
Input
Stack
71
Time 3
Input
Stack
72
Time 4
Input
Stack
73
Time 5
Input
Stack
74
Time 6
Input
Stack
75
Time 7
Input
Stack
76
Time 8
Input
Stack
accept
Formalities for PDAs
77
78
Transition function:
79
Transition function:
Formal Definition
80
Pushdown Automaton (PDA)
States
Input
alphabet
Stack
alphabet
Transition
function
Final
states
Stack
start
symbol
Initial
state
Instantaneous Description
81
Current
state
Remaining
input
Current
stack
contents
82
Input
Stack
Time 4:
Example:
Instantaneous Description
83
Input
Stack
Time 5:
Example:
Instantaneous Description
84
We write:
Time 4
Time 5
85
A computation:
86
For convenience we write:
Formal Definition
87
Language of PDA :
Initial state
Final state
88
Example:
PDA :
89
PDA :
90
PDA :
Therefore: