(b) {x | x contains an odd number of b’s}
(c) {x | x contains an even number of a’s or an odd number of b’s}
(d) {x | x contains an even number of a’s and an odd number of b’s}
42. Give the DFA accepting the sets of strings matching the following
regular expressions:
(a) (000* + 111*)*
(b) (01 + 10) (01 + 10) (01 + 10)
(c) (0 + 1 (01*0)*1)*
43. Show that the following sets are not regular.
(a) {
|
}
a b
n m
n m
= 2
(b) { { , , } |
*
x a b c
x
∈
is a palindrome}
(c) { { , , } |
*
x a b c
∈
the length of x is a square}
44. Consider the NFA shown below.
(a) Construct an equivalent DFA.
(b) Give an equivalent regular expression.
45. Convert the NDA to equivalent DFA for each of the following:
(a)
(b)
46. Give the regular expressions for each of the following subsets of {a, b}
* .
(a) {x | x does not contain the substring a}
(b) {x | x does not contain the substring ab}
(c) {x | x does not contain the substring aba}
47. Match each NFA with an equivalent regular expression.
(a)
DFA and NFA
107
s 0
s 1
s 2
s 3
a,b
a
a
b
s 0
s 1
s 2
s 3
a,b
a
a
b
a,b
q 0
q 1
q 2
0
0
1
0
1
q 0
q 1
a
b
a
b