This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Obtaining the regular Expression from the finite automata – 1”.

1. L1 is accepted by the NFA, obtained by changing the accepting state of M to a non-accepting state and vice versa. Which of the following statements is true?

a) L1 = {0, 1}* – L

b) L1 = {0, 1}* – L

c) L1 ⊆ L

d) L1=L

View Answer

Explanation: Either it takes 0 or 1 or iterations of it or none.compilers-questions-answers-Obtaining the regular Expression from the Finite automata

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) N^{2}

b) 2^{N}

c) 2N

d) N!

View Answer

Explanation: 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}

View Answer

Explanation: 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

View Answer

5. The number of states in DFA that accepts the language L(M) ∩ L(N) is _________

a) 0

b) 1

c) 2

d) 3

View Answer

Explanation: In DFA M: all strings must end with ‘a’. In DFA N: all strings must end with ‘b’. So the intersection is empty. For an empty language, only one state is needed.

6. 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

View Answer

Explanation: 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 (C).

7. 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

View Answer

Explanation: L3 is simple to guess, it is regular.

Below is DFA for L1.

L1 is interesting. The important thing to note

about L1 is length of x is greater than 0.

8. The reorganizing capability of NDFA and DFA

a) May be different

b) Must be different

c) Must be same

d) None of the mentioned

View Answer

Explanation: Given any NDFA one can construct an equivalent DFA.

9. 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) All of the mentioned

d) None of the mentioned

View Answer

Explanation: Strings of odd numbers of zeros can be generated by regular expression (00)*0.

10. Which of the following pairs of regular expression are equivalent?

a) 1(01)* and (10)*1

b) X(xx)* and (xx)*x

c) All of the mentioned

d) None of the mentioned

View Answer

Explanation: R1 and R2 are reverse of each other. If ant one of them can be generated them the other can be generated as well.

**Sanfoundry Global Education & Learning Series – Compilers.**

To practice all areas of Compilers, __here is complete set of 1000+ Multiple Choice Questions and Answers__.