# Theory of Computation Chapter 2 - Automata

（請搭配達叔的投影片一起服用）

**自動機 (Automaton)**， 是一種抽象機器，是**有限狀態機 (Finite State Machine, FSM)** 的數學模型。
* 可分為**確定有限自動機 (Deterministic Finite Automata)** 和**非確定有限自動機 (Nondeterministic Finite Automata)**
* 如果一個自動機的輸出是「是 / 否」，則稱這個自動機為**Accepter**
* 如果一個自動機的輸出是某個語言的字串，則稱這個自動機為 **Transducer**
> Figure 1. 一個 Finite Accepter

## Deterministic Finite Accepters (DFA)

* 確定有限自動機可以表示為一個五元組 $\langle Q, \Sigma, \delta, q_{0}, F \rangle$
* $Q$ 是**狀態 (states)** 的集合
* $\Sigma$ 是符號的有限集合，我們稱為這個自動機接受的語言的**字母表 (alphabet)**
* $\delta$ 是**轉移函式 (transitions)** ，即 $\delta : Q \times \Sigma \rightarrow Q$
* $q_{0}$ 是**起始狀態 (initial state)**， 即自動機在還未處理輸入的時候的狀態。每個自動機只會有一個，且 $q_{0} \in Q$
* $F$ 是**終止狀態 (final states)**， 是 $Q$ 中的狀態的子集，即 $F \subseteq Q$

### DFA 的特色

* 一次只吃一個字
* 所有的轉移函式皆為一對一函數，亦即 input 一個字串，最後只可能抵達一個狀態，不可能同時走到多個狀態
* 對於每一個狀態，所有可能的轉移函式都必須補滿，即要填滿這張表
> Figure 2. 一個DFA的轉移函式，所有可能的路徑都必須補滿
* 從 $q$ 到 $q'$ 有一條路徑 (walk)， 中間經過的字串為 $w$， 若且唯若 $\delta^*(q, w) = q'$
* $\delta^*$ 為**擴充轉移函式 (Extended Transition Function)**， 是一次吃入長度為 1 以上的 input 的轉移函式，即 $$\delta^*:Q\times \Sigma^* \rightarrow Q$$ 遞迴定義為 $$\begin{equation} \begin{cases} \delta^*(q, \lambda) = q\\ \delta^*(q, w\sigma) = \delta(\delta^*(q, w), \sigma) \end{cases} \end{equation} $$

### DFA 接受的語言

* 給定一個 DFA， 叫作 $M$， 則 $L(M)$ 為一個集合，包含所有可以被 $M$ 接受的字串，稱為 $M$ 可以接受的語言 (Language accepted by $M$)
* 就定義上來說，因為 $M = (Q, \Sigma, \delta, q_{0}, F)$， 所以 $M$ 可以接受的語言可以表示為 $L(M) = \{ w \in \Sigma^{*}: \delta^{*}(q_{0}, w) \in F \}$
* 一個語言 $L$ 是正規語言 (Regular Language)， 若且唯若存在一個 DFA $M$ 可以接受這個 $L$， 即 $L = L(M)$
* 如果要證明一個 $L$ 是正規語言，就看這個 $L$ 畫不畫的出一個可以接受他的 DFA， 如果可以，就是正規的，如果不行，那就不是

## Nondeterministic Finite Accepters (NFA)

* 非確定有限自動機可以表示為一個五元組 $\langle Q, \Sigma, \delta, q_{0}, F \rangle$
* $Q$ 是**狀態 (states)** 的集合
* $\Sigma$ 是符號的有限集合，我們稱為這個自動機接受的語言的**字母表 (alphabet)**
* $\delta$ 是**轉移函式 (transitions)**， $\delta : Q \times (\Sigma \cup \lambda) \rightarrow 2^{Q}$ （$Q$ 的Power set）
* $q_{0}$ 是**開始狀態 (initial state)**，即自動機在還未處理輸入的時候的狀態。每個自動機只會有一個，且 $q_{0} \in Q$
* $F$ 是**終止狀態 (final states)**， 是 $Q$ 中的狀態的子集，即 $F \subseteq Q$

### NFA的特色

* 轉移函式可以為一對多函數，亦即輸入一個字串，最後可能可以走到一個以上的狀態
* 允許**空字串轉移 (Lambda Transition)**， 即可以在不讀入任何一個符號的情況下在不同的狀態之間移動
* 允許轉移函式輸出為空集合，即可以有一個狀態沒有任何轉移，走不到下一個狀態

### NFA接受的語言

* 給定一個 NFA， 叫作 $M$， 則 $L(M)$ 為一個集合，包含所有可以被 $M$ 接受的字串，稱為 $M$ 可以接受的語言 (Language accepted by $M$)
* 因為 $M = (Q, \Sigma, \delta, q_{0}, F)$， 所以 $M$ 可以接受的語言可以表示為 $L(M) = \{ w \in \Sigma^{*}: \delta^{*}(q_{0}, w) \cup F \neq \emptyset \}$
* 因為 NFA 的轉移函式的輸出是個集合，所以要確認一個語言是否被 NFA 接受，需檢查這個集合當中的元素是否同樣存在於終止狀態中（即和 $F$ 的交集是不是空集合）
* 只要一個輸入字串有一種走法可以被 NFA 消化完畢，並且最終停留的狀態屬於終止狀態，則這個字串就是可以被 NFA 接受的字串（就算這個字串可以走到的其它路徑不被接受，或是其它路徑無法走完這個字串，也無所謂）
* 由於 NFA 對於一個輸入有多個輸出（存在不確定性輸出），在描述某些問題時，用 NFA 會比用 DFA 來的容易描述
* 儘管如此， **NFA 和 DFA 可以接受的語言，其實是同一個集合（都是正規語言）**

## Equivalence of DFA and NFA

* 定義： 若兩個有限自動機 $M_1$ 和 $M_2$ 是等價的，則他們接受的語言集合要一模一樣，即 $L(M_1) = L(M_2)$
* 如果有一種自動機可以接受另一種自動機無法接受的語言，則我們說前者是比後者還要強力的 (Powerful)
* DFA 其實是 NFA 的子集（所有的轉移函式都是一對一函數的 NFA = DFA）， 而 DFA 和 NFA 的計算能力其實是一樣強的（他們可以接受的語言集合是一樣的）

### DFA v.s. NFA

* 透過證明 「DFA 接受的語言等同於 NFA 接受的語言」，可以證明 DFA 和 NFA 的運算能力是等價的
* 證明 「DFA 接受的語言 $\subseteq$ NFA 接受的語言」
* 因為 DFA 基本上就是一個沒有空字串轉移，所有的轉移函式都是一對一函數的 NFA， 所以 DFA 是 NFA 的特例（子集）， DFA 可以接受的語言因此屬於 NFA 可以接受的語言
* 證明 「NFA 接受的語言 $\subseteq$ DFA 接受的語言」
* 如果每一個 NFA 都可以透過增加 trap state， 補全轉移函式之類的步驟轉換為一個等價的 DFA， 則 NFA 可以接受的語言就會包含於 DFA 可以接受的語言
* 可以使用以下演算法（似 BFS）
1. 從 NFA 當中的 $q_0$ 出發，將其令為 $q_0'$， 視為 DFA 當中的 $q_0$
2. 寫出 $q_0$ 對於每一個字母的轉移函式，其結果為一個一個的集合，將每一個集合都視為一個在 DFA 當中的狀態
3. 若這個集合以前沒看過，就將他加入 DFA 當中成為一個新的狀態，如果有看過，就將轉移函數填上
4. 每看到一個新的狀態，就檢查該狀態對應的集合裡頭所有的狀態，將他們在原本的 NFA 裡頭的轉移函式的結果都記錄下來，成為一個新的集合
5. 回到步驟三，直到再也沒有新的狀態出現
6. 完成的表格即為 DFA 的完整狀態轉移表，可以畫出一個DFA
7. 在 DFA 的每一個狀態當中，只要裡頭對應到的 NFA 的狀態中有一個是終止狀態，就將該 DFA 的狀態也視為終止狀態
* 因為 NFA 是有限狀態機，所以上述演算法終究會有停止的一天，因此所有的 NFA 都可以轉為一個等價的 DFA， 因此 NFA 可以接受的語言包含於 DFA 可以接受的語言
* 由於兩個集合互相包含對方，證明兩個集合相等，所以DFA可以接受的語言等於NFA可以接受的語言
* NFA 的化簡與特例
* 所有的 NFA 都可以轉為只有一個終止狀態的等價的 NFA
* 只要製造一個新的終止狀態，將原本的所有終止狀態都透過空字串轉移跳到新的終止狀態，再將原本的終止狀態改為普通的狀態就可以了
* 只吃空字串的 NFA
* 就是有一個終止狀態，但是沒有轉移函式會跳到那個狀態的 NFA

## Reduction of the Number of States in FA*

### 冗贅的狀態機

* 一個語言可以用很多不同的 DFA 和 NFA 來描述，也就是說，可以接受一個語言的 DFA / NFA 並不是唯一的
* 在眾多的 FA 當中，如果一個 FA 所用到的狀態愈少，表示他可以用愈簡單 / 愈少的轉移函式來描述一個語言，則當要將這個 FA 實作成硬體/軟體的時候，所使用的成本就會愈低，所以我們比較喜歡狀態較少的那個
* 既然用少數的狀態就可以接受一個語言，則表示多出來的狀態有一些其實是等價於其他狀態的
* 所謂的等價，指的是這兩個狀態在吃進一樣的字串的時候，他們最後轉移到的狀態都是一樣的
* 給定兩個狀態 $p$ 和 $q$， 當 $\delta^*(p,w)\in F \rightarrow \delta^*(q,w)\in F$ 且 $\delta^*(p,w)\notin F \rightarrow \delta^*(q,w)\notin F$， 我們說 $p$ 和 $q$ 是不可分辨的 (indistinguishable)， 也就是兩個狀態是等價的
* 不可分辨的兩個狀態當中，有一個是冗贅的 (redundant)， 可以直接用另一個狀態取代

### 分辨哪些狀態是冗餘的（這段不確定，要翻課本）

* 可以透過以下演算法來辨識一個 DFA 當中的哪些狀態是冗餘的
1. 先將所有狀態區分為是終止狀態的和不是終止狀態的兩群
2. 在所有已分出來的群中，重複進行以下檢查
a. 對於任意兩個狀態，檢查是否每一個字母輸入後他們的輸出狀態都在同一群當中（都會終止或是都不會終止）
b. 如果是，那就表示這兩個狀態無法分辨，其中一個是冗餘的
c. 如果否（有至少一個字串會掉進不同的群），那就表示兩個狀態可以分辨，可以將其中一個分出來變成另一個群
3. 如果最後分離出來的群跟 DFA 的狀態數一樣多（或是說，每個群裏面都只有一個狀態）的話，就表示這 DFA 當中沒有冗餘的狀態

### 最小化狀態機

* *參考離散數學 Chapter 7, p.58*