Given two languages $L_1$ and $L_2$, give a language $L'$ that both $L_1$ and $L_2$ reduce to.

I'm not quite how to do this. I know the solution is fairly simple. I know I can somehow represent $L'$ in terms of $L_1$ and $L_2$. Then I need to create a computable function that maps $L_1$ to $L'$ and either use the same function, or create a separate function that maps $L_2$ to $L'$.

  • 2
    $\begingroup$ And what have you tried, where did you get stuck? $\endgroup$ – Raphael Nov 17 '15 at 7:55

Hint: Try $L=0L_1\cup1L_2$. Can you see how to map $L_1$ to $L$ and $L_2$ to $L$? You have to be slightly clever; you might want to use prefixes other than 0 and 1.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.