Classical

Theory Of Computation MCQ - Context free languages

46:  

Which of the following statement is wrong ?

A.

 Any regular language has an equivalent context-free grammar.

B.

Some non-regular languages can’t be generated by any context-free grammar

C.

Intersection of context free language and a regular language is always context-free

D.

All languages can be generated by context- free grammar

 
 

Option: D

Explanation :


47:  

Consider a grammar :

                            G = ( { x , y ) , { s , x , y } , p ,  s)

where elements of parse :

                                   S--> x y
                                   S -->y x
                                   x--> x z
                                   x--> x
                                   y--> y
                                   z--> z


The language L generated by G most accurately is called

A.

Chomsky type 0 

B.

Chomsky type 1

C.

 Chomsky type 2

D.

Chomsky type 3

 
 

Option: D

Explanation :


48:  

Consider a grammar :

                      G = { { S } , { 0 , 1 } , p , s } 

where elements of p are:

                     S --> ss
                     S--> 0S1
                     S--> 1S0
                     S--> empty


The grammer will generate

A.

regular language

B.

 context-free language

C.

context-sensitive language

D.

 recursive enumerable language

 
 

Option: A

Explanation :


49:  

  A grammar that produces more than one parse tree for some sentence is called

A.

ambiguos

B.

unambigous

C.

regular

D.

none of these

 
 

Option: A

Explanation :


50:  

Given a grammar G a production of G with a dot at some position of the right side is called 

A.

LR (0) item of G 

B.

LR (1) item of G

C.

both (a) and (b)

D.

none of these

 
 

Option: A

Explanation :




Suggest an improvement