Epsilon 轉移與 Epsilon 閉包

一個什麼都不讀的轉移

在上一篇導覽裡，非確定型有限自動機靠「複製」取得它的威力：讀到單一個符號時，它可以分裂成好幾份副本，各自追逐不同的下一個狀態，而只要有任何一份副本停在接受狀態，它就接受。那裡的轉移把「狀態加符號」送到一整個狀態集合——也就是你已經見過的集合值轉移，寫作 delta(q, a) = {p1, p2, ...}。現在，我們加上最後一項、近乎調皮的自由。

一個 epsilon 轉移（epsilon-move）是兩個狀態之間的一支箭，它標的不是真正的符號，而是 epsilon（ε），也就是空字串。機器可以在任何時刻沿著這支箭滑過去，不從輸入讀任何東西、也不消耗任何字元。把它想成機器內部的一道暗門：你正站在狀態 q，瞥見一道標著 ε、通往狀態 p 的暗門，你大可以在讀下一個符號之前、之後、或乾脆取而代之地免費掉進去。允許這種轉移的 NFA，就叫做 epsilon-NFA。

何苦如此？能咬合在一起的機器

epsilon 轉移帶來的好處，是「黏合」。假設你有一台辨認「結尾是 ab」的小機器，另一台辨認「只由 c 組成」的小機器，而你想要一台辨認「兩者擇一」的機器。有了 epsilon 轉移，幾秒就能造好：加一個全新的起始狀態，畫兩支 epsilon 箭，各自指向兩台舊機器的起始狀態。讀取者只要免費地「猜」要進入哪一台子機器就好。沒有任何符號被改寫，也沒有任何轉移要靠手工合併——空字串的箭頭把線路全接好了。

正規運算就是這樣被機械地實現出來的：從機器 A 的結尾拉一支 epsilon 箭到機器 B 的起始，就得到串接；一支繞回去的 epsilon 箭，就得到 Kleene 星號。等我們把一個正規表示式轉成機器時，你會看到這招被認真地用上——標準的建構法不過就是一份用 epsilon 箭把小零件咬合起來的食譜。所以 epsilon 轉移與其說是一種新的能力，不如說是一個萬用接頭，就像樂高積木上的那些凸點。

Epsilon 閉包：所有你能免費漂過去的地方

一旦有了免費移動，「我現在在哪個狀態？」就成了問錯的問題。對的問題是：「在不讀任何東西的情況下，我現在『可能』身處哪些狀態？」答案就是狀態 q 的 epsilon 閉包，常寫作 E(q) 或 ECLOSE(q)：從 q 沿著零支或多支 epsilon 箭可達的所有狀態所成的集合。它永遠包含 q 本身（沿著零支箭），接著是所有一個 ε 跳之外的狀態，再來是這些狀態的 ε 鄰居，如此下去，直到再也冒不出新狀態為止。

讓工作清單一開始只裝著 q，並把 q 標記為「已在閉包中」。
從工作清單拿出任一個狀態 r，檢視從 r 射出的每一支 epsilon 箭。
對於該箭通往的每一個狀態 s：若 s 是新的，就把它加進閉包，也加進工作清單；若 s 早已在其中，就略過它。
重複到工作清單為空。被標記的那個集合就是 E(q)——而它是有限的，所以這個過程一定會停下來。

這不過是一次只走 epsilon 箭的圖搜尋（廣度優先或深度優先），又因為狀態只有有限多個，它不可能永遠跑下去——就算 ε 箭兜成一個圈也無妨，因為一個狀態一旦被標記，你就再也不會重訪它。要在一台 epsilon-NFA 上跑一個字串，你交替做兩件事：先取你目前所在位置的 epsilon 閉包，再從當前整個狀態集合讀進一個真正的符號，然後再取一次 epsilon 閉包。閉包負責把每一處免費的漂移都掃乾淨；而讀符號這一步，是唯一會讓你指著輸入的手指往前移的動作。

一個迷你的逐步演練

這裡有一台字母表為 Σ = {a, b} 的三狀態 epsilon-NFA。起始狀態是 q0，唯一的接受狀態是 q2。狀態 q0 有一支 epsilon 箭通到 q1，q1 有一支 epsilon 箭通到 q2；至於讀真正符號的箭：q0 讀 a 回到 q0，q1 讀 b 回到 q1。請注意，沒有任何符號讀取能真的「抵達」q2——q2 永遠只能靠著沿 ε 箭漂移才到得了。

States: q0 (start), q1, q2 (accept)

   epsilon            epsilon
q0 ---------> q1 ---------> q2
 |             |
 | a           | b
 v             v
q0            q1            (q2 has no outgoing arrows)

E(q0) = {q0, q1, q2}     <- drift q0 -> q1 -> q2 for free
E(q1) = {q1, q2}
E(q2) = {q2}

Run on input "a":
  start set      = E(q0)        = {q0, q1, q2}
  read 'a'       : q0--a-->q0   (q1,q2 have no 'a' arrow) = {q0}
  closure again  = E(q0)        = {q0, q1, q2}
  end of input. q2 is in the set -> ACCEPT

起始狀態的閉包已經包含接受狀態 q2，所以連空輸入都被接受；讀一個 'a' 會繞回 q0，然後再次漂移到 q2。

把它慢慢推一遍，紀律就清楚了。你從來不是待在單一個狀態裡；你待在一個狀態「集合」裡，而那個集合永遠對 epsilon 轉移封閉。一個字串被接受，剛好就在讀完最後一個符號、再做最後一次閉包之後，你手上握著的那個集合與接受狀態至少共用一個狀態的時候。這種「狀態集合」的觀點並非巧合——它正是後面某篇導覽裡子集合建構法的種子，在那裡，每一個這樣的集合都會變成一台等價確定型機器的單一狀態。

沒有新的威力——只有新的方便

人們很容易以為免費移動會讓機器變強。它不會。epsilon 閉包正是讓我們得以「移除」每一支 ε 箭的工具：把每個讀符號的轉移 delta(q, a) 換成「先閉包、再讀 a、再閉包一次」，那些空字串的箭就化進普通的箭裡消失了。結果是一台辨認同一個語言的、樸素的 NFA。所以 DFA、NFA、以及 epsilon-NFA 三者的表達力完全相等——這就是三種模型的等價性，而它們各自恰好辨認那些正規語言，不多也不少。

請牢牢記住上一篇那個誠實的教訓：非確定性——無論是靠複製還是靠免費移動——是一種用來精簡地書寫機器的數學裝置，既不是隨機行為，也不是免費的平行硬體。真實的 CPU 並不能掉進暗門。等你真要在一台實際的電腦上跑一台 epsilon-NFA 時，你會藉著追蹤整個可達狀態集合來一次模擬所有分支，而這正是上面那個「先閉包再讀」的迴圈。方便是給人類設計者的；機器仍舊老老實實地做工，而這份代價會在後面以 NFA 轉 DFA 的膨脹顯現出來。