Session 1: �Pushdown Automata- Definitions – Moves-Deterministic pushdown automata
By
Dr. Ashok Kumar
Amity School of Engineering & Technology
Pushdown Automaton -- PDA
2
Input String
Stack
States
Amity School of Engineering & Technology
3
Initial Stack Symbol
Stack
Stack
bottom
special symbol
stack
head
top
Amity School of Engineering & Technology
The States
4
Input
symbol
Pop
symbol
Push
symbol
Alternatively
Amity School of Engineering & Technology
5
top
input
stack
Replace
Amity School of Engineering & Technology
6
Push
top
input
stack
Amity School of Engineering & Technology
7
Pop
top
input
stack
Amity School of Engineering & Technology
8
No Change
top
input
stack
Amity School of Engineering & Technology
9
Pop
top
input
stack
A Possible Transition
empty
Amity School of Engineering & Technology
10
input
A Bad Transition
The automaton Halts in state
and Rejects the input string
Empty stack
HALT
Amity School of Engineering & Technology
11
input
A Bad Transition
The automaton Halts in state
and Rejects the input string
Empty stack
HALT
Amity School of Engineering & Technology
12
No transition is allowed to be followed
When the stack is empty
Empty stack
Amity School of Engineering & Technology
13
Pop
top
input
stack
A Good Transition
Amity School of Engineering & Technology
A Pushdown automata PDA M can be defined as 7 Tuples
Amity School of Engineering & Technology
Amity School of Engineering & Technology
Non-Determinism
16
These are allowed transitions in a
Non-deterministic PDA (NPDA)
Amity School of Engineering & Technology
17
Transition function:
Amity School of Engineering & Technology
18
Transition function:
Amity School of Engineering & Technology
Difference between NPDA and DPDA�
Amity School of Engineering & Technology
Amity School of Engineering & Technology
21
A string is accepted if there is
a computation such that:
All the input is consumed
AND
The last state is a final state
At the end of the computation,
we do not care about the stack contents
Amity School of Engineering & Technology
22
A string is rejected if in every
computation with this string:
The input cannot be consumed
OR
The input is consumed and the last state is not a final state
OR
The stack head moves below the bottom of the stack
Amity School of Engineering & Technology
23
Example: Design PDA for the language
Amity School of Engineering & Technology
24
Execution Example:
Input
current
state
Time 0
Stack
Amity School of Engineering & Technology
25
Input
Time 1
Stack
Amity School of Engineering & Technology
26
Input
Stack
Time 2
Amity School of Engineering & Technology
27
Input
Stack
Time 3
Amity School of Engineering & Technology
28
Input
Stack
Time 4
Amity School of Engineering & Technology
29
Input
Stack
Time 5
Amity School of Engineering & Technology
30
Input
Stack
Time 6
Amity School of Engineering & Technology
31
Input
Stack
Time 7
Amity School of Engineering & Technology
32
Input
Time 8
accept
Stack
Amity School of Engineering & Technology
33
The input string
is accepted by the NPDA:
Amity School of Engineering & Technology
Another example
34
NPDA
Amity School of Engineering & Technology
Pushing Strings
35
Input
symbol
Pop
symbol
Push
string
Amity School of Engineering & Technology
36
top
input
stack
Push
pushed
string
Example:
Amity School of Engineering & Technology
Problems
# 4:
Design a NPDA to accept the following Language:
L(M) = { anb2n , n ≥ 0 }
37
Amity School of Engineering & Technology
38
q3
q1
q4
q2
λ,λ 🡪 λ
a,λ 🡪 00
b,0 🡪 λ
b,0 🡪 λ
λ,$ 🡪$
a
a
b
b
b
b
$
Stack
Input String
Time - 0
Amity School of Engineering & Technology
Problems
# 5:
Design a NPDA to accept the following Language:
L(M) = { wcwR, w∈{a,b}* }
39
Amity School of Engineering & Technology
L(M) = { wcwR, w∈{a,b}* }
40
Amity School of Engineering & Technology
# 6:
Design a NPDA to accept the following Language:
L(M) = { anbn+mcm , n ≥0, m≥1 }
41
Amity School of Engineering & Technology
42
q2
q1
b,0 🡪λ
b,0 🡪 λ
a, λ 🡪 0
q3
a
a
b
b
b
c
Input String
$
Stack
Time 0
b,$ 🡪 0$
b, λ 🡪 0
q4
c,0 🡪 λ
c,0 🡪 λ
q5
λ,$ 🡪 $
Amity School of Engineering & Technology