Compilers Multiple Choice Questions on “Minimization of DFA”.
1. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2* U L1*?
a) €
b) a*
c) All of the mentioned
d) None of the mentioned
Answer: a
Clarification: L1* = * which is { }.
2. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
a) 1, 2, 3
b) 2, 3, 4
c) 1, 2, 4
d) 1, 3, 4
Answer: c
Clarification: The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’.
3. Which one of the following languages over the alphabet {0,1} is described by the regular expression?
(0+1)*0(0+1)*0(0+1)*
a) String with substring 00
b) String with at most two 0’s
c) String containg at least two 0’s
d) None of the mentioned
Answer: c
Clarification: The regular expression has two 0′s surrounded by (0+1)* which means accepted strings must have at least 2 0′s.
4. Which one of the following is FALSE?
a) Every NFA can be converted to DFA
b) Every subset of a recursively enumerable set is recursive
c) All of the mentioned
d) None of the mentioned
Answer: b
Clarification: Every subset of a recursively enumerable set is recursive.
5. Which of the following are regular sets?
I. { an b2m | n>=0, m>=0}
II. {an bm |n=2m}
III. {an bm | n!= m}
IV {xcy |x,y€{a,b)*}
a) I and IV
b) I and III
c) I and only
d) IV
Answer: a
Clarification: We can write DFA for both I and IV.