Classical

Theory Of Computation MCQ - Context free languages

56:  

Context-free grammar can be recognized by

A.

finite state automation

B.

2-way linear bounded automata

C.

push down automata 

D.

both (b) and (c)

 
 

Option: D

Explanation :


57:  

 The language L = (0n 1n 2n where n > 0) is a

A.

context free language

B.

context-sensitive language

C.

regular language

D.

recursive enumerable language

 
 

Option: B

Explanation :


58:  

Context free language are closed under

A.

union, intersection

B.

union, kleene closure

C.

intersection, complement

D.

complement, kleene closure

 
 

Option: B

Explanation :

For Reference Click Here


59:  

 If G = ({S}, {a}, {S -> SS), S),

then language generated by G is

A.

L (G) =  φ

B.

L(G) = an

C.

L (G) =  a*

D.

L (G) = anban

 
 

Option: A

Explanation :


60:  

Grammar
S —> a,
S —> A3A,
 A3 —> A1, A3, A2 ,
A3 —> A1 A2, A1
A2—> aA2A1 ,
 A1a —> a A1
A2a —> aA2
A1A4 —> A4a,
A2A4 —> A5a, 
A2A5 —> A5a,
A5 —> a

                         generates

A.

an^2

B.

n2a

C.

2an

D.

none of these

 
 

Option: A

Explanation :




Suggest an improvement