30. Determine a regular grammar that generates the regular set recognized
by the finite state automaton shown in Fig.
31. Prove that the set {
|
, , ,
}
o
n
n n
1
0 1 2
=
KK made up of all strings
consisting of a block of 0s followed by a block of an equal number of 1
s ,
is not regular.
32. Express each of the following sets using a regular expression.
(a) the set of strings of one or more 0s followed by a 1.
(b) the set of strings of two or more symbols followed by three or more
0s.
33. Show that if A is a regular set, then set A
R , the set of all reversals of
strings in A, is also regular.
34. Find an NDA which recognizes the set 0
* 1
* .
35. Show that the set {0
2n 1
n } is not regular using pumping lemma.
36. Show that the set of palindromes over {0,1} is not regular using
pumping lemma.
37. Convert the NFA to DFA of the NFA shown below.
38. Convert the regular expression (
)
*
ab a
∪
to an NFA.
39. Convert the regular expression (
)
*
a b aba
∪
to an NFA.
40. Using pumping lemma show that the following languages are not
regular.
(a) L
n
n n n
1
0 1 2
0
=
≥
{
|
}
(b) L
a
n
n
2
2
0
=
≥
{
|
} (a
n
2 means a string of 2
n a’s).
41. Give regular expressions for each of the following subsets of {a, b}
* .
(a) {x | x contains an even number of a’s }
106
Theory of Automata, Formal Languages and Computation
3
1
2
b
a
a,b
a
ε
s 0
s 1
s 2
Start
1
0
0
0
1
1