edited by
752 views
3 votes
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?

  1.  L1 is decidable and L2 is undecidable.  
  2.  L1 is regular and L2 is CFL.
  3.  L1 is recursive and L2 is recursively enumerable.
  4.  L1 is decidable and L2 is decidable.
edited by

Please log in or register to answer this question.

Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,184 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
297 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
205 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4