Register

#TOC NPTEL ASSIGNMENT Question about reducibility

695 views

1 Answer

1 1 vote

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. 
Voting & Accepting an answer helps improve the community
← Previous · S->AA/ab A->Bd/null...Next → · #algorithms #databas...
← Previous in category · Applied roots test s...Next in category → · #RegularExpression
Position:
Show:

Related questions

1 1 vote
1 1 answer
1.6k
1.6k views
sunaina rawat asked Oct 2, 2017
1,565 views
Reducibility
Why this is incorrect? For any two languages A and B, if A ⊆ B, then A is reducible to B.
2 2 votes
1 answers 1 answer
1.2k
1.2k views
shikharV asked Jan 4, 2016
1,174 views
Question on reducibility
Please check if the given answer is correct or not.
0 0 votes
0 0 answers
1.4k
1.4k views
srestha asked Sep 12, 2018
1,433 views
Reducibility
State which are TRUE and which are FALSE (Question 1) and 2) both have same options)$1)$If there is an algorithm for polynomial time reduction from A to B?$2)$ if there i...
0 0 votes
0 0 answers
445
445 views
HeadShot asked Dec 4, 2018
445 views
Doubt : Reducibility
$Question:$ https://gateoverflow.in/63261/%23made-easy $Approach:$ A is reduced to B . Here reduction is done at polynomial time.Here B is solved in polynomial time. S...