Classical

Theory Of Computation MCQ - Context free languages

26:  

 Given A = (0,1) and L = A*. If R = (0n 1n, n > 0) , then language L ∪ R and R are respectively

A.

regular, regular

B.

not regular, regular

C.

regular, not regular

D.

context free, not regular

 
 

Option: D

Explanation :


27:  

Define for a context free language

L ≤ {0 ; 1} init (L) = {u/uv  ε L for some v in {0,1}}

(in other words, init (L) is the set of prefixes of L)

Let L {w/w is noempty and has an equal number of 0’s and 1’s)

Then init (L) is

A.

set of all binary strings with unequal number of 0’s and 1’s

B.

set of all binary strings including the null string

C.

set of all binary strings with exactly one more 0’s than the number of 1’s or 1 more  than the number of 0’s

D.

none of these

 
 

Option: B

Explanation :


28:  

 If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

A.

LL2

B.

L1  ∩ L2

C.

L1 ∩ R

D.

L1 ∪ L2

 
 

Option: B

Explanation :


29:  

Consider a grammar with the following productions

                                     S-->   aab | bac | aB
                                     S -->  α S | b
                                     S -->  α b b | ab
                                     Sα --> bdb | b


               The above grammar is 

A.

Context free

B.

regular

C.

context sensitive

D.

LR ( k )

 
 

Option: C

Explanation :


30:  

What can be said about a regular language L over {a} whose minimal finite state automation has two states?

A.

L must be { an | n is odd}

B.

L must be { an | n is even}

C.

 L must be {an | > 0}

D.

Either L must be {an | n is odd}, or L must be {an | n is even}

 
 

Option: B

Explanation :




Suggest an improvement