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(

$E{Q}_{DFA}$ )是不是 decidable

• $A_{DFA}$

• $A_{NFA}$

• $E_{DFA}$

• $E{Q}_{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
  $Al{l}_{CFG}$)

$E{Q}_{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$ 的

$T{M}^{\prime }$ 可能會進入 infinite loop。

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

$TM$ 的數量可以用所有 alphabet 的組合來表示 ( i.e.

$\sum ^{\ast }$ )，
Language 的數量可以用

$\sum ^{\ast }$ 的 power set 來表示 ( i.e.

$P(\sum ^{\ast })$ )

其中

$\sum ^{\ast }$ 是 countable infinite set，但

$P(\sum ^{\ast })$ 是 uncountable infinite set，所以 Language 的數量遠大於

$TM$ 的數量。

證明在課本有，使用對角線證明。
用

$TM$ 來模擬的話，類似邏輯謬論（ 一位理髮師只幫不剪自己頭髮的人理頭髮，試問理髮師會不會理自己的頭髮 ）

Undecidable Language

Undecidable 具有一個特殊的性質，即

A language is decidable iff it is Turing-recognizable and co-Turing-recognizable

其中我覺得關鍵是 Every string

$w$ is either in

$A$ or

$\bar{A}$，
因為在 simulate

$TM$ 上的

$TM$ 中所接受的 input 是 Language ，every language

$L$ is not either in

$TM$ or

$\overline{TM}$，
不像在 simulate

$CFL$ or

$DFA$ 中的

$TM$ 接受的 input 是 string (

$\sum ^{\ast }$ )。

最後我們可以用上述性質來證明

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

• $REGULA{R}_{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
    $REGULA{R}_{TM}$.
  • Construct
    $M_2$ which accept strings in
    $\{0^n{1}^n|n\ge 0\}$ if
    $M$ does not accept
    $w$, and to recognize regular language
    $\sum ^{\ast }$ if
    $M$ accepts
    $w$, so that
  • $S$ = 1. Run
    $R$ on
    $M2$
    2. If
    $R$ accepts then
    $accept$; if R rejects then
    $reject$.

• $E{Q}_{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
    $E{Q}_{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 數量為
  $qn{g}^n$ where
  $TM$ has
  $q$ states and
  $g$ symbols

上述性質可以使得

$A_{LBA}$ 是 decidable！

因為最多只需要經過

$qn{g}^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 的步驟課本有

• $AL{L}_{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
    $AL{L}_{CFG}$.
  • $S$
    $accetp$ if
    $R$ rejects;
    
    $reject$ if
    $R$ accepts.

$CFG$ ( i.e.

$PDA$ ) 如何 check 不生成特定 computation history 的步驟課本有

• $E{Q}_{CFG}$ is undecidable
  • Let
    $S$ is the
    $TM$ simulate
    $AL{L}_{CFG}$, and
    $R$ is the
    $TM$ simulate
    $E{Q}_{CFG}$.
  • Let
    $G_0$ 生成
    $\sum ^{\ast }$
  • $S$
    $accept$ if
    $R(G,G_0)$ accepts;
    
    $reject$ if
    $R(G,G_0)$ rejects.

---

$A_{TM}{\le }_m\bar{X}$ hints that

$\bar{X}$ is undecidable and

$X$ is not turing-recognizable.

Note that

${\bar{A}}_{TM}{\le }_m\overline{\stackrel{―}{X}}\Rightarrow {\bar{A}}_{TM}{\le }_{m}X$, and

${\bar{A}}_{TM}$ is not turing-recognizable, so is X.