# Reduction from 2 finite languages when one doesn't include epsilon and the other does

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,

• $\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$. Commented Jul 12, 2021 at 17:49
• 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. Commented Jul 12, 2021 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}.$$