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. 
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. 
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.  L_{1 }L_{2} 
B.  L_{1 }∩ L_{2} 
C.  L_{1} ∩ R 
D.  L_{1 }∪ L_{2} 
Option: B Explanation : Click on Discuss to view users comments. 
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. Vandana said: (8:40am on Thursday 15th February 2018)
Sa> b This production is contracting , hence this can't be CSG , this grammer is unrestricted grammer.

What can be said about a regular language L over {a} whose minimal finite state automation has two states?
A.  L must be { a^{n}  n is odd} 
B.  L must be { a^{n}  n is even} 
C.  L must be {a^{n}  > 0} 
D.  Either L must be {a^{n}  n is odd}, or L must be {a^{n}  n is even} 
Option: B Explanation : Click on Discuss to view users comments. Shruti said: (1:49pm on Wednesday 19th August 2015)
Option [A] will also generate a minimal dfa of two states.
Arjun Rou said: (9: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: (5:00pm on Sunday 25th June 2017)
C SHOULD BE CORRECT ANSWER.
Vandana said: (8: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.
