250+ TOP MCQs on The NFA with epsilon – Moves and Answers

Compilers Multiple Choice Questions on “The NFA with epsilon – Moves”.

1. S –> aSa| bSb| a| b; the language generated by the above grammar is the set of ____________
a) All palindromes
b) All odd length palindromes
c) Strings beginning and ending with the same symbol
d) All even length palindromes

Answer: b
Clarification: The strings accepted by language are {a, b, aaa, bbb, aba, bab,}. All the strings are odd length palindromes.

2. 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) strings with the substring 00
b) strings with at most two 0’s
c) strings with at least two 0’s
d) strings beginning and ending with either 0 or 1

Answer: c
Clarification: The RE having 2 0’s padded by (0+1)* which means accepted strings must have at least 2 0’s.

3. Which one is a FALSE statement?
a) There exists a unique DFA for every regular language
b) NFA can always are converted to a PDA
c) Complement of CFL is always recursive
d) Every NDFA can be converted to a DFA

Answer: d
Clarification: Deterministic PDA cannot handle languages or grammars with ambiguity, but NDFA can handle with ambiguous languages as well as context-free grammar. Hence not every Ndfa can be converted to DFA.

4. Match the following.

      Group 1                       Group 2
P. Regular expression        1. Syntax analysis
Q. Pushdown automata         2. Code generation
R. Dataflow analysis         3. Lexical analysis
S. Register allocation       4. Code optimization

a) P-4. Q-1, R-2, S-3
b) P-3, Q-1, R-4, S-2
c) P-3, Q-4, R-1, S-2
d) P-2, Q-1, R-4, S-3

Answer: b
Clarification: Regular grammar relates to lexical analysis
Pushdown automata relates to Syntax analysis
Data flow analysis is Code optimization
Register allocation is code generation.

5. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below.

L1 = {ambmcanbn | m, n >= 0 }
L2 = {aibjck | i, j, k >= 0 }

Then L is?
a) Not recursive
b) Regular
c) Context free but not regular
d) None of the mentioned

Answer: c
Clarification: The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb,} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is L1 ∩ L2 = {akbkc | k >= 0} which is not regular but context free.

6. Does epsilon ring any change in the automata.
a) Yes
b) No

Answer: b
Clarification: It adds nothing new to the automata.