Classical

Theory Of Computation MCQ - Context free languages

61:  

 If L1 = {x  | x is a palindrome in (0 + 1)*}
                 L2 = {letter (letter + digit)* };
                 L3 = (0n 1n 2n | n > 1}
                 L4 = {ambnam+n | m, n > 1}


then which of the following statement is incorrect ?

A.

L1 is context free language and L3 is context sensitive language

B.

L2 is a regular set and L4 is not a context free language

C.

Both L1 and L2 are regular sets

D.

Both L3 and L4 are context-sensitive languages

 
 

Option: A

Explanation :


62:  

A grammar to generate
{ (ab)n I n ≥ 1 }  ∪  { (ba)n I n ≥ 1 }
is constructed as

A.

S ---> S1, S1 ---> abS1,  S1 ---> ab,  S ---> S2, S2 —> baS2, S2 —> ba

B.

S ---> S, Sl ---> aS1, S1 ---> ab, S ---> S2, S2 ---> bS2, S2 —> bc

C.

S —> S1,  S1—>S2, S2 —> S1a, S1 —> ab, S2 —> ba

D.

none of these

 
 

Option: C

Explanation :


63:  

Consider the grammar
                             S ---> PQ | SQ | PS
                             P ---> x
                             Q-->   y

To get a string of n terminals, the number of productions to be used is

A.

n2

B.

n + 1

C.

2n

D.

2n - 1

 
 

Option: D

Explanation :


64:  

 What is the highest type number which can be applied to the following grammar ?
S —> Aa, A —> Ba, B —> abc

A.

Type 0

B.

Type 1

C.

Type 2

D.

Type 3

 
 

Option: C

Explanation :


65:  

 Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production

A  —> aB  {print “(1)” A —> c {print “1”),
B —> Ab  {print *2”}.


When parser is aaacbbb, then string printed

A.

0202021

B.

1202020

C.

1020202

D.

none of these

 
 

Option: A

Explanation :




Suggest an improvement