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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Shruti said: (8:49pm on Wednesday 19th August 2015)
Option [A] will also generate a minimal dfa of two states.
Arjun Rou said: (4:16am on Wednesday 4th January 2017)
F.A accepting odd no of {a} also have a minimum two states. According to me right option should be been option (D)
VIJAY said: (12:00am on Monday 26th June 2017)
C SHOULD BE CORRECT ANSWER.

Write your comments here:





Suggest an improvement