Compilers Multiple Choice Questions on “Obtaining the regular Expression from the finite automata”.
1. Which of the following pairs of regular expression are equivalent?
a) 1(01)* and (10)*1
b) X(xx)* and (xx)*x
c) 1(01)* and (10)*1 & X(xx)* and (xx)*x
d) None of the mentioned
Answer: c
Clarification: R1 and R2 are reverse of each other. If ant one of them can be generated them the other can be generated as well.
2. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least?
a) N2
b) 2N
c) 2N
d) N!
Answer: c
Clarification: If the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
3. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?
a) L must be {an| n is odd}
b) L must be {an| n is even}
c) L must be {an| n is even}
d) Either L must be {an | n is odd}, or L must be {an | n is even}
Answer: d
Clarification: There are two states. When first state is final, it accepts even no. of a’s. When second state is final, it accepts odd no. of a’s.
4. How many minimum states are required to find whether a string has odd number of 0’s or not?
a) 1
b) 2
c) 3
d) 4
Answer: b
5. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X0. How are X1 and X2 are related?
X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}
Which one of the following represents the strings in X0?
a) 10 (0* + (10)*)1
b) 10 (0* + (10)*)*1
c) 10 (0* + (10)*)*1
d) 10 (0 + 10)*1 + 110 (0 + 10)*1
Answer: c
Clarification: The smallest possible string by given grammar is “11”.
X0 = 1X1
= 11X2 [Replacing X1 with 1X2]
= 11 [Replacing X2 with λ]
The string “11” is only possible with option 10 (0* + (10)*)*1.
6. Which of the following languages is/are regular?
L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w
L2: {anbm ⎪m ≠ n and m, n≥0}
L3: {apbqcr ⎪ p, q, r ≥ 0}
a) L1 and L3 only
b) L2
c) L2 and L3 only
d) L3 only
Answer: a
7. The reorganizing capability of NDFA and DFA is?
a) May be different
b) Must be different
c) Must be same
d) None of the mentioned
Answer: c
Clarification: Given any NDFA one can construct an equivalent DFA.
8. Which of the following is not regular?
a) String whose length is perfect square and consists of 0s
b) Palindromes consisting of 0’s and 1’s
c) String whose length is perfect square and consists of 0s & Palindromes consisting of 0’s and 1’s
d) None of the mentioned
Answer: c
Clarification: Strings of odd numbers of zeros can be generated by regular expression (00)*0.