Just did a test about the subject that had the following question:

I know it seems trivial and my first reaction was "well of course its true" but the epslilon kinda threw me off.

$L_2$={ab,$\epsilon$} $L_1$={a} , is there a computable reduction from $L_1\leq L_2$ ,: True Or False

I assumed by contradiction that its true and did the following :

My idea was that if we always reject epsilon , then the starting state would always reject on the empty string , therefor no reduction would exists.

, if $\epsilon\notin L_1$ then the computable function f must uphold: $f(\epsilon)\notin L_2\iff \epsilon\notin L_1$ Therefor the turning machine will always stop on the empty string , so she'll also stop on $\epsilon\cdot a=a$ therefor $f(\epsilon a)=f(a)\notin L_1$ in contradiction to the assumption

Now the answer was true apparently but I can't really understand why , I'm also not 100% sold on my solution , but since I managed to prove it I just went with it , so I assume that I have some mistake in the part of $f(\epsilon a)=f(a)$.


  • $\begingroup$ $\varepsilon$ is not in $L_1$, so your "if and only if" simplifies to $f(\varepsilon) \not\in L_2$. I'm not sure what the argument about the Turing machine stopping is. The reduction is a computable total function $f$, therefore any Turing machine computing $f$ will halt for all possible input strings $x$ regardless of whether $x \in L_1$ or $x \not\in L_1$. $\endgroup$
    – Steven
    Jul 12 at 17:49
  • $\begingroup$ Thanks , I thought that since she isn't accepting $f(\epsilon)$ then she must always reject any input which I'm still not sure which its true or not , but the answer below gave a reduction which finds a reduction and overcomes this problem. $\endgroup$ Jul 12 at 17:59

Here a possible function $f$ that provides the reduction from $L_1$ to $L_2$.

$$ f(x) = \begin{cases} \varepsilon & \mbox{if $x=a$} \\ b & \mbox{otherwise} \end{cases}. $$


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.