# 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 Answer Report Discuss 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 Answer Report Discuss 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. L1 L2 B. L1  ∩ L2 C. L1 ∩ R D. L1 ∪ L2 Answer Report Discuss 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 ) Answer Report Discuss Option: C Explanation : Click on Discuss to view users comments. Vandana said: (6:40am on Thursday 15th February 2018) Sa---> b This production is contracting , hence this can't be CSG , this grammer is unrestricted grammer. 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} Answer Report Discuss Option: B Explanation : Click on Discuss to view users comments. Shruti said: (10:49am on Wednesday 19th August 2015) Option [A] will also generate a minimal dfa of two states. Arjun Rou said: (7:16pm on Tuesday 3rd 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: (2:00pm on Sunday 25th June 2017) C SHOULD BE CORRECT ANSWER. Vandana said: (6:43am on Thursday 15th February 2018) All the options are correct wrt the given question, we can have a dfa with 2 states for all the given options. Write your comments here: