467 views

1 Answer

1 votes
1 votes

According to me, option A should be correct. 

Consider L1 is regular and the query being is L1 also context free?

now lets reduce L1 to any general language L2. 

  1.  its clear that L1 complement is also regular and L2 complement will also be any generalized language. Hence L1 complement can be reduced to L2 complement.
  2. L2 complement may or may not be reduced to L1 complement as general language can be regular or CFL or any other.
  3. similarly L2 cannot be reduced to L1
  4. with L1 not being kleen closure lets say L1 has any particular string so that makes L1 as decidable. Since L1 is reduced to L2 this means that L2 can or cannot be decidable. Hence option D is also false. 

Related questions

1 votes
1 votes
1 answer
1
sunaina rawat asked Oct 2, 2017
1,022 views
Why this is incorrect? For any two languages A and B, if A ⊆ B, then A is reducible to B.
2 votes
2 votes
1 answer
2
shikharV asked Jan 4, 2016
833 views
Please check if the given answer is correct or not.