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
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
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
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-3, Q-4, R-1, S-2
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
6.

Convert the NFA to DFA.
A.  
 B.  
 C.  

All of the mentioned

 D.  

None of the mentioned
7.

Does epsilon ring any change in the automata.
A.  

Yes

 B.  

No
8.

NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA.
A.  

True

 B.  

False
9.

E(q) is known ε-closure of q.
A.  

True

 B.  

False
10.

ε-transitions does not add any extra capacity of recognizing formal.
A.  

True

 B.  

False