# The note of Formal Language and the Theorem of Computation

###### tags: `NCTU`, `Formal Language`, `Theorem of Computation`
## Chap 4 Decidability
### 4.1 Decidable Language
#### For Regular Language
為了要證明 $A_{DFA}$ 是 decidable，
先說明 acceptance problems for $DFAs$ ( 在一個特定的 $DFA$ 上檢測特定字串 $w$ 是否 accept )，可以以 language 的方式來呈現，即$A_{DFA} = \{<B,w>|B$ is a $DFA$ that accepts input string $w\}$
所以上述問題等同於判斷$<B,w> \in A_
{DFA}$ 是否成立。

回到 $A_{DFA}$ 是否 decidable 的問題，其若且唯若 $<B,w>$ 是否 decidable 。

>Decidable 指的是是否存在一個 $TM$ 可以決定
>這個語言，且不存在 infinite loop。
>當存在一個演算法可以判斷這個問題即表示找到此 $TM$

上述的說明可以推廣成 whether the laguage of a finite automaton is empty( $E_{DFA}$ ) and whether two finite automaton are equivalent( $EQ_{DFA}$ )是不是 decidable

* $A_{DFA}$
* $A_{NFA}$
* $E_{DFA}$
* $EQ_{DFA}$

* 結論：如果能夠找到一個演算法，能夠使得 acceptance problem 可解，即代表此問題為 Turing recognizable，且因為找到的演算法不具 infinite loop 所以又稱為 Turing decidable
>演算法舉例在課本有

#### For Contex-Free Language
證明方法和 Regular 一樣，皆是找出一個演算法。

其中的 proof idea 我覺得比較有趣的地方是，當判斷一個 $w$ 是否屬於一個 $CFG$ 的時候，若從 $S$ 開始展開，過程中如果出現 $w$ 即代表 $w \in CFG$，這個方法看似沒問題，但在考慮 $w \notin CFG$ 的時候上述方式卻會進入 infinite loop，那麼就代表 $A_{CFG}$ 是 Turing recognizable 而不是 decidable？

解法，先將$CFG$轉換成 CNF，根據 CNF 的性質，長度為 n 的 $w$，最多只需要 $2n-1$ 個 steps 就能找到，依照這個特性設計的演算法就不會陷入 infinite loop 的窘境，故 $A_{CFG}$ 是 decidable
* $A_{CFG}$
* $E_{CFG}$
* Every CFL is decidable (not $All_{CFG}$)
> $EQ_{CFG}$ is not decidable

### 4.2 Undecidability
電腦看似強大到每種 problem 都可解，但是仍然存在 unsolvable problem，舉例來說，去設計一個演算法來判斷一個演算法是否正確，像是課堂作業要求學生實作排序演算法，老師助教們需要去判別學生所實作的 sort algorithm 是不是在 any inputs 之下都會正確運作。

此種問題可以看成是一個 language，即
> $A_{TM}=\{<M,w>|M$is a $TM$ and $M$ accepts $w\}$

而 $A_{TM}$ 僅僅只有 Turing-recognizable。

那是因為目前不存在有比 $TM$ 更強大的計算模型去包括 $TM$ 本身 ( 像是 $DFA$ 就可以用 $TM$ 去 simulate ) 或是設計出有效率的方式能找到推演方法（像是 $CFG$ 存在 $CNF$ 去避免進入 infinite loop ），所以當輸入一個 $TM$ 會 infinite loop 的 $w$ 負責模擬 $TM$ 的 $TM'$ 可能會進入 infinite loop。

* Key point: 是否存在 $TM$ 不接受的 inputs?
* i.e. Language 的數量是否比 $TM$ 能表示的數量還要多？

$TM$ 的數量可以用所有 alphabet 的組合來表示 ( i.e. $\sum ^*$ )，
Language 的數量可以用 $\sum ^*$ 的 power set 來表示 ( i.e. $P(\sum ^*)$ )

其中 $\sum ^*$ 是 countable infinite set，但 $P(\sum ^*)$ 是 uncountable infinite set，所以 Language 的數量遠大於 $TM$ 的數量。
>證明在課本有，使用對角線證明。
用 $TM$ 來模擬的話，類似邏輯謬論（ 一位理髮師只幫不剪自己頭髮的人理頭髮，試問理髮師會不會理自己的頭髮 ）

#### Undecidable Language
Undecidable 具有一個特殊的性質，即
>A language is decidable iff it is Turing-recognizable and co-Turing-recognizable
>
>

其中我覺得關鍵是 <mark>Every string $w$ is either in $A$ or $\overline A$</mark>，
因為在 simulate $TM$ 上的 $TM$ 中所接受的 input 是 Language ，every language $L$ is not either in $TM$ or $\overline {TM}$，
不像在 simulate $CFL$ or $DFA$ 中的 $TM$ 接受的 input 是 string ( $\sum ^*$ )。

最後我們可以用上述性質來證明 $\overline {A_{TM}}$ 不是 decidable，因為 $A_{TM}$ 不是 decidable

### Ch5

* $E_{TM}$ is undecidable
* Use the knowledge of $A_{TM}$ is undecidable
* Let $S$ is the $TM$ simulate $A_{TM}$, and $R$ is the $TM$ simulate $E_{TM}$.
* Construct $M_1$ which accept when $input = w$ and reject otherwise, so that
* $S$ = 1. Run $R$ on $M_1$
2. If $R$ accepts then $reject$; if R rejects then $accept$.

* $REGULAR_{TM}$ is undecidable
* Use the knowledge of $A_{TM}$ is undecidable
* Let $S$ is the $TM$ simulate $A_{TM}$, and $R$ is the $TM$ simulate $REGULAR_{TM}$.
* Construct $M_2$ which accept strings in $\{0^n1^n\ |\ n \geq 0\}$ if $M$ does not accept $w$, and to recognize regular language $\sum ^*$ if $M$ accepts $w$, so that
* $S$ = 1. Run $R$ on $M2$
2. If $R$ accepts then $accept$; if R rejects then $reject$.

* $EQ_{TM}$ is undecidable
* Use the knowledge of $E_{TM}$ is undecidable
* Let $S$ is the $TM$ simulate $E_{TM}$, and $R$ is the $TM$ simulate $EQ_{TM}$, and $M_1$ is a $TM$ that rejects all inputs.
* $S$ = 1. Run $R$ on input $<M, M_1>$
2. if $R$ accepts then $accept$; if $R$ rejects then $reject$

#### Linear Bounded Automaton
是 $TM$ 的一種變形，多了 tape 長度的限制，舉例來說，當 input length 為 n 的時候，tape ( memory ) 長度只需要 n 的線性大小即可，因得其名。

* $LBA$ 的 configuration 數量為 <mark>$qng^n$</mark> where $TM$ has $q$ states and $g$ symbols

上述性質可以使得 $A_{LBA}$ 是 decidable！

因為最多只需要經過 $qng^n$ 個 steps 就能得知是否 $accept$ ( i.e. $LBA$ never have infinite loop )

* $A_{LBA}$ is decidable
* $E_{LBA}$ is undecidable
* Proof idea is similar to $E_{TM}$
* 建立一個 $LBA$ accepts if input 是 $M$ accepts $w$ 的 computation history, otherwise reject all inputs.
* Let $S$ is the $TM$ simulate $A_{TM}$, and $R$ is the $TM$ simulate $E_{LBA}$.
* $S$ = $accept$ if $R$ rejects;
$reject$ if $R$ accepts.
> $LBA$ 如何 check computation history 的步驟課本有
* $ALL_{CFG}$ is undecidable
* 建立一個 $CFG$ 在 $M$ accepts $w$ 時會產生除了該 computation history 之外的所有字串，而 $M$ does not accept $w$ 時則產生所有字串。
* Let $S$ is the $TM$ simulate $A_{TM}$, and $R$ is the $TM$ simulate $ALL_{CFG}$.
* $S$ $accetp$ if $R$ rejects;
$reject$ if $R$ accepts.
> $CFG$ ( i.e. $PDA$ ) 如何 check 不生成特定 computation history 的步驟課本有

* $EQ_{CFG}$ is undecidable
* Let $S$ is the $TM$ simulate $ALL_{CFG}$, and $R$ is the $TM$ simulate $EQ_{CFG}$.
* Let $G_0$ 生成 $\sum ^*$
* $S$ $accept$ if $R(G, G_0)$ accepts;
$reject$ if $R(G, G_0)$ rejects.

---

$A_{TM} \leq_m \overline X$ hints that $\overline X$ is undecidable and $X$ is not turing-recognizable.
> Note that $\overline A_{TM} \leq_m \overline {\overline X}\Rightarrow \overline A_{TM} \leq_m X$, and $\overline A_{TM}$ is not turing-recognizable, so is X.