Compilers Questions and Answers – The NFA with epsilon – Moves – 1

This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “The NFA with epsilon – Moves – 1”.

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
View Answer

Answer: b
Explanation: 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?


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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: d
Explanation: 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.

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

Answer: b
Explanation: 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
View Answer

Answer: c
Explanation: 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. Convert the NFA to DFA.
Find the NFA from the given diagram
a) Find the DFA from the given diagram
b) Find the new states from the given diagram
c) All of the mentioned
d) None of the mentioned
View Answer

Answer: a
Explanation: Initially Q is empty. Then since the initial state of the DFA is {0}, {0} is added to Q.
Since 2( 0 , a ) = { 1 , 2 } , { 1 , 2 } is added to Q and ( { 0 } , a ) = { 1 , 2 }.
Since 2( 0 , b ) = , is added to Q and ( { 0 } , b ) = .
At this point Q = { {0} , { 1 , 2 }, }. Similarly ( { 1 , 2 } , b ) = { 1 , 3 } . Hence { 1 , 3 } is added to Q . Similarly ( { 1 , 3 } , a ) = { 1 , 2 } and ( { 1 , 3 } , b ) = . Thus there are no new states to be added to Q . Since the transitions from all states of Q have been computed and no more states are added to Q, the conversion process stops here.

7. Does epsilon ring any change in the automata.
a) Yes
b) No
View Answer

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

Sanfoundry Global Education & Learning Series – Compilers.

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

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.