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


0

9.9。構造一個從Accepts-$ \ lambda $到問題accepts-$ \ {\ lambda \} $的約簡:給定一個TM $ T $,$ L(T)= \ {\ lambda \} $嗎?

問題來自馬丁的語言和計算理論導論

我不確定減少的工作原理,儘管我不確定幾件事。很容易看出,如果內部機器(計算" accepts-$ \ {\ lambda \} $")接受,那麼外部機器也必須接受,但是不清楚其他機器是否也接受。如何確保這一點?

1

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