16. Construct a PDA accepting L by empty store where
L a b a n
j
j n n
=
≥
≥
{
|
,
}
1
0
17. Construct a PDA accepting {
:
,
}
a b c n
j
j n n
≥
≥
1
1 by final state.
18. Constuct a CFG generating {
|
} {
|
}
a b n
a b m
n n
m
m
≥ ∪
≥
1
1
2
. Using this
CFG, construct a PDA accepting the given set by empty store.
19. Using Pumping lemma show that the language L a b c i
i i i
=
≥
{
|
}
0 is not
context free.
20. Using Pumping lemma show that the language
L a b c
m n p
m n p
=
≤ ≤ ≤
{
|
}
0
is not a CFL.
21. Using Pumping Lemma prove that the language L ww w
=
∈
{ |
{ , }
*
0 1 is
not a CFL.
22. Consider the set of all strings over {a, b} with no more than twice as
many a’s as b’s:
{ { , } | # ( ) # ( )}
*
x a b
a x
b x
∈
≤ 2
(a) Give a CFG for this set, and prove that it is correct.
(b) Give a PDA for this set. Show sample runs on the input strings
aabbaa, aaabbb and aaabaa.
23. Consider the set
a b c
a b c n
n n n
* * * — {
|
}
≥ 0
the set of all strings of a’s followed by b’s followed by c’s such that the
number of a’s, b’s and c’s are not all equal.
(a) Give a CFG for the set, and prove that your grammar is correct.
(b) Give an equivalent PDA.
24. Show that { , } — {
|
}
*
a b
a b
n
n n
≥
2
0 is not context free.
SHORT QUESTIONS AND ANSWERS
1. What is PDA and NDPDA?
PDA means Push Down Automata and NDPDA means
non- deterministic Push Down Automata.
2. Define an NDPDA.
An NDPDA is defined by the 7-tuple
M
Q
q Z F
= ( , , , , , , )
Σ Γ δ 0
182
Theory of Automata, Formal Languages and Computation