In one of the above comments it is mentioned--

L2 recursive and L1 r.e. is possible when both are recursive as a recursive language is also a r.e. language.

I don't know rest :/

Option b may be true if both L1 and L2 are regular languages.

Dark Mode

426 views

3 votes

If a language L1 is polynomially reduced to the language L2 and L2 is polynomially reduced to the language L1, then which of the following cannot be TRUE?

- L1 is decidable and L2 is undecidable.
- L1 is regular and L2 is CFL.
- L1 is recursive and L2 is recursively enumerable.
- L1 is decidable and L2 is decidable.

0

Can someone explain why B and C are true?

I just learnt that

- If A is reducible to B and B is Recursive language then A is also Recursive language.
- If A is reducible to B and B is Recursive Enumerable language then A is also Recursive Enumerable language.
- If A is reducible to B and A is not Recursive Enumerable language then B is also not Recursive Enumerable language.

But I don’t know the actual logic behind it and I also don't know that If P is polynomially reducible to Q then If P is Regular implies Q has to Regular or not?

If someone can explain the logic or just share some reference then it will be very helpful

0