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)

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

DFA 的特色

• 一次只吃一個字
• 所有的轉移函式皆為一對一函數，亦即 input 一個字串，最後只可能抵達一個狀態，不可能同時走到多個狀態
• 對於每一個狀態，所有可能的轉移函式都必須補滿，即要填滿這張表
  

Figure 2. 一個DFA的轉移函式，所有可能的路徑都必須補滿

• 從
  $q$ 到
  $q^{\prime }$ 有一條路徑 (walk)， 中間經過的字串為
  $w$， 若且唯若
  ${\delta }^{\ast }(q,w)=q^{\prime }$
• ${\delta }^{\ast }$ 為擴充轉移函式 (Extended Transition Function)， 是一次吃入長度為 1 以上的 input 的轉移函式，即
  $${\delta }^{\ast }:Q\times {\mathrm{\Sigma }}^{\ast }\to Q$$ 遞迴定義為
  $$\{\begin{array}{l}{\delta }^{\ast }(q,\lambda )=q\\ {\delta }^{\ast }(q,w\sigma )=\delta ({\delta }^{\ast }(q,w),\sigma )\end{array}$$

DFA 接受的語言

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

Nondeterministic Finite Accepters (NFA)

• 非確定有限自動機可以表示為一個五元組
  $⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩$
  • $Q$ 是狀態 (states) 的集合
  • $\mathrm{\Sigma }$ 是符號的有限集合，我們稱為這個自動機接受的語言的字母表 (alphabet)
  • $\delta$ 是轉移函式 (transitions)，
    $\delta :Q\times (\mathrm{\Sigma }\cup \lambda )\to 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,\mathrm{\Sigma },\delta ,q_0,F)$， 所以
  $M$ 可以接受的語言可以表示為
  $L(M)=\{w\in {\mathrm{\Sigma }}^{\ast }:{\delta }^{\ast }(q_0,w)\cup F\ne \mathrm{\varnothing }\}$
  • 因為 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^{\prime }$， 視為 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 }^{\ast }(p,w)\in F\to {\delta }^{\ast }(q,w)\in F$ 且
    ${\delta }^{\ast }(p,w)\notin F\to {\delta }^{\ast }(q,w)\notin F$， 我們說
    $p$ 和
    $q$ 是不可分辨的 (indistinguishable)， 也就是兩個狀態是等價的
  • 不可分辨的兩個狀態當中，有一個是冗贅的 (redundant)， 可以直接用另一個狀態取代

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

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

最小化狀態機

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