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
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?
(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
View Answer
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
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.
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
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
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.
a) 
b) 
c) All of the mentioned
d) None of the mentioned
View Answer
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
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.
- Check Computer Science Books
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Compiler Design Books
- Practice MCA MCQs
