# Compilers Questions and Answers – Obtaining the regular Expression from the Finite automata – 1

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

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) N2
b) 2N
c) 2N
d) N!

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}

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

Explanation: 2 minimum states are required to find whether a string has odd number of 0’s or not.

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

a) 0
b) 1
c) 2
d) 3

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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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 10 (0* + (10)*)*1.

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

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 is?
a) May be different
b) Must be different
c) Must be same
d) None of the mentioned

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) String whose length is perfect square and consists of 0s & Palindromes consisting of 0’s and 1’s
d) None of the mentioned

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) 1(01)* and (10)*1 & X(xx)* and (xx)*x
d) None of the mentioned

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.