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