0
$\begingroup$

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)$.

Thanks,

Improve this question
$\endgroup$
2
  • $\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
    Commented Jul 12, 2021 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$
    – David Pitts
    Commented Jul 12, 2021 at 17:59

1 Answer 1

Reset to default
0
$\begingroup$

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}. $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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