# 從問題"可接受的空字符串"減少為"空字符串的語言"

9.9。構造一個從Accepts-$\ lambda$到問題accepts-$\ {\ lambda \}$的約簡：給定一個TM $T$，$L（T）= \ {\ lambda \}$嗎？

Call $L_1=\{\langle M \rangle\mid M\text{ accepts }\lambda\}$ and $L_2=\{\langle M \rangle\mid M\text{ accepts only }\lambda\}$, where $\langle M\rangle$ denotes the description of the TM $M$. We wish to establish a mapping reduction $L_1 \le_\text{M} L_2$.

To do this, we want a mapping, $f$, from TM descriptions to TM descriptions such that $$\langle M\rangle\in L_1 \Longleftrightarrow f(\langle M\rangle)\in L_2$$ For a TM description $\langle M\rangle$, we'll define $f(\langle M\rangle)=\langle N\rangle$ where

N(x) =
if x = lambda
run M on input lambda
if M accepts
accept


Now what happens with this mapping?

• If $M(\lambda)$ accepts (so $\langle m\rangle\in L_1)$, $N$ will accept $\lambda$ and no other string, so $\langle N\rangle\in L_2$.
• If $M(\lambda)$ doesn't accept (so $\langle M\rangle\notin L_1)$, $N$ will accept no input string, so $L(N)=\varnothing$ and thus $\langle N\rangle\notin L_2$.

That's exactly what we need to establish the reduction $L_1 \le_\text{M} L_2$.