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 correct ?

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 :

Click on Discuss to view users comments.

Kajal Kansal said: (12:51am on Wednesday 9th April 2014)
L1 is surely cfl and l3 is csl then how this is the right answer.i think c is the right answer as L1 is not regular set because of palindrome
Vandana said: (5:12pm on Thursday 15th February 2018)
Only option A is true , rest all 3 are false , so in question they should ask for the correct answer. Then option A will be the right choice.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Vandana said: (5:16pm on Thursday 15th February 2018)
Given grammer is a left linear grammer , so it is type 3 grammer , so correct option should be option d.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



Related MCQ