More Problems on
Push Down Automaton
A. Senthil - Asst. Professor/CSE 1
Problems
# 4:
Design a NPDA to accept the following Language:
L(M) = { anb2n , n ≥ 0 }
A. Senthil - Asst. Professor/CSE 2
Time - 0
Input String
a a b b b b
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 3
Time - 1
Input String
a a b b b b
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 4
Time - 2
Input String
a a b b b b
0
0
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 5
Time - 3
Input String
a a b b b b 0
0
0
0
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 6
Time - 4
Input String
a a b b b b 0
0
0
0
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 7
Time - 5
Input String
a a b b b b
0
0
0
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 8
Time - 6
Input String
a a b b b b
0
0
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 9
Time - 7
Input String
a a b b b b
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 10
Time - 8
Input String
a a b b b b
“Accept”
$
a, 00 b,0
Stack
, q b,0 ,$ $
q1 q q4
2 3
A. Senthil - Asst. Professor/CSE 11
Problems
# 5:
Design a NPDA to accept the following Language:
L(M) = { wcwR, w{a,b}* }
A. Senthil - Asst. Professor/CSE 12
L(M) = { wcwR, w{a,b}* }
a, a a, a
b, b b, b
q0 c, q1 , $ $ q2
A. Senthil - Asst. Professor/CSE 13
Execution Example: Time 0
Input
a b c b a
$
Stack
a, a a, a
b, b b, b
q0 c, q1 , $ $ q2
A. Senthil - Asst. Professor/CSE 14
Time 1
Input
a b c b a
a
$
Stack
a, a a, a
b, b b, b
q0 c, q1 , $ $ q2
A. Senthil - Asst. Professor/CSE 15
Time 2
Input
b
a b c b a
a
$
Stack
a, a a, a
b, b b, b
q0 c, q1 , $ $ q2
A. Senthil - Asst. Professor/CSE 16
Time 3
Input
b
a b c b a
a
$
Stack
a, a a, a
b, b b, b
q0 c, q1 , $ $ q2
A. Senthil - Asst. Professor/CSE 17
Time 4
Input
b
a b c b a
a
$
Stack
a, a a, a
b, b b, b
q0 c, q1 , $ $ q2
A. Senthil - Asst. Professor/CSE 18
Time 5
Input
a b c b a
a
$
Stack
a, a a, a
b, b b, b
q0 c, , $ $ q2
q1
A. Senthil - Asst. Professor/CSE 19
Time 6
Input
a b c b a
$
Stack
a, a a, a
b, b b, b
accept
q0 c, q1 , $ $ q2
A. Senthil - Asst. Professor/CSE 20
Problems
# 6:
Design a NPDA to accept the following Language:
L(M) = { anbmcn+m , n0, m0 }
A. Senthil - Asst. Professor/CSE 21
L(M) = { anbmcn+m , n0, m0 }
a,$ 0$
a,0 00 b,1 11
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 22
Input String
Time 0
a a b c c c
a,$ 0$
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 23
Input String
Time 1
a a b c c c
a,$ 0$ 0
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 24
Input String
Time 2
a a b c c c
0
a,$ 0$ 0
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 25
Input String
Time 3
a a b c c c
1
0
a,$ 0$ 0
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 26
Input String
Time 4
a a b c c c
1
0
a,$ 0$ 0
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 27
Input String
Time 5
a a b c c c
0
a,$ 0$ 0
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 28
Input String
Time 6
a a b c c c
a,$ 0$ 0
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 29
Input String
Time 7
a a b c c c
a,$ 0$ 0
a,0 00 b,1 11 $
Stack
b,$ 1$
b,0 10 q5
, q q
q1 accept
2 3
c,1
q c,0
A. Senthil - Asst. Professor/CSE
4 30
Problems
# 6:
Design a NPDA to accept the following Language:
L(M) = { anbn+mcm , n0, m1 }
A. Senthil - Asst. Professor/CSE 31
Input String
Time 0
a a b b b c
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q2 q3 q4
q5
A. Senthil - Asst. Professor/CSE 32
Input String
Time 1
a a b b b c
0
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q2 q3 q4
q5
A. Senthil - Asst. Professor/CSE 33
Input String
Time 2
a a b b b c
0
0
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q2 q3 q4
q5
A. Senthil - Asst. Professor/CSE 34
Input String
Time 3
a a b b b c
0
0
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q q q
2 3 4
q5
A. Senthil - Asst. Professor/CSE 35
Input String
Time 4
a a b b b c
0
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q q q
2 3 4
q5
A. Senthil - Asst. Professor/CSE 36
Input String
Time 5
a a b b b c
0
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q q q
2 3 4
q5
A. Senthil - Asst. Professor/CSE 37
Input String
Time 6
a a b b b c
0
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q q q
2 3 4
q5
A. Senthil - Asst. Professor/CSE 38
Input String
Time 7
a a b b b c
$
Stack
a, 0 b,0 b, 0 c,0
b,0 b,$ 0$ c,0
q1 q q q
2 3 4
“Accept” q5
A. Senthil - Asst. Professor/CSE 39
Problems
# 7:
Design a NPDA to accept the following Language:
L(M) = { a3bncn , n0}
A. Senthil - Asst. Professor/CSE 40
L(M) = { a3bncn , n0}
a, a,
qc qb qa
b, b c, b
b, b c, b , $ $ q
q0 q1 q2 3
A. Senthil - Asst. Professor/CSE 41
Representation of PDA
By
Flow chart Structure
A. Senthil - Asst. Professor/CSE 42
Shapes & Notations:
Start Reject Accept
Read Push Pop
A. Senthil - Asst. Professor/CSE 43
Example:
Design a PDA that accepts the Language
L = {anbn , n0}
By flow chart method
A. Senthil - Asst. Professor/CSE 44
Start
b
Accept
Read
a b $
a
Push a Pop Read Pop
$ a a
Reject Reject Reject
A. Senthil - Asst. Professor/CSE 45
# 7:
Design a NPDA to check the well-formedness
of parenthesis in the given string.
A. Senthil - Asst. Professor/CSE 46
Start
(
( )
Read Pop
$
Push (
( Reject
Pop
$
Reject
Accept
A. Senthil - Asst. Professor/CSE 47
