Compilers Multiple Choice Questions & Answers (MCQs) on “Minimization of DFA”.
1. Which one of the following is TRUE?
a) The language L={a^n b^n |n>0 } is regular
b) The language L={a^n |n is prime } is regular
c) The language L={w|w has 3k+1 b’s for some k } is regular
d) None of the mentioned
Answer: c
Clarification: Only for this option we can build a FA.
2. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences of (110)’s as (011)’s}.
Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences of (000)’s as (111)’s}.
Which one of the following is TRUE?
a) L1 is regular but not L2
b) L2 is regular
c) L1 and L2 are regular
d) Neither of them are regular
Answer: a
Clarification: L1 is regular let us considering the string 011011011011 . Number of times 011 has occurred is 4 but also its occurrence is 3. Also if the string is ending with 011 we can make a 110 . Now the next string: 110110110110 in this 110 has occurred 4 times and 011 3 times which already satisfy the .
3. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is _____________
a*b*(ba)*a*
a) 2
b) 3
c) 4
d) 5
Answer: b
Clarification: baa is not regular so 3.