JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

封閉性：用語言搭建新語言

你已經會造 DFA、NFA，也會寫正規表示式——這是同一個家族的三張臉。本篇交給你一間工坊：拿你已信任的正規語言，把它們組合起來（聯集、交集、補集、星號、反轉），並保證結果「仍然」是正規的。每一種組合都附帶一台你能親手建出的機器，而同一套工具箱還兼任一個偷偷證明某語言「不是」正規的辦法。

一個永遠不漏的工具箱

想像一箱樂高積木，附帶一個安靜的承諾：用這些積木拼出來的任何東西，都還能放回同一個箱子裡。正規語言的行為恰好就像這個箱子。拿任意幾個正規語言，用某些標準方式扣在一起，結果「仍然」是正規的——永遠逃不出這個家族。我們說正規語言對這些運算是封閉的（closed），而這個封閉性正是讓我們用簡單、可信賴的元件組裝出複雜辨識器的關鍵。

這是頭條清單。若 L 與 M 都是正規語言，則以下也都是：聯集（屬於任一者的字串）、交集（同時屬於兩者的字串）、L 的補集（字母表上「不」屬於 L 的所有字串）、串接 LM（一個 L 字串黏在一個 M 字串前面）、Kleene 星號 L*（把零個或多個 L 字串黏接起來）、以及 L 的反轉（每個字串倒著拼）。每一項都不是靠揮手帶過，而是用明確的構造（construction）來證明：一個食譜，輸入你手上已有的自動機或正規表示式，機械化地建出結果的那一台。本篇接下來就一台一台地走過這些食譜。

一次跑兩台機器：積構造法

假設你想要一台機器同時追蹤「兩件事」——比如「含偶數個 a」「且」「以 b 結尾」。與其發明一台聰明的單一自動機，不如讓兩台小機器並排、同步、在同一段輸入上一起跑，並隨時記下「每一台」目前所在的位置。這對「成對的快照」就是積構造法的全部想法：一台新的 DFA，其狀態是一對對的狀態，分別來自原本的兩台機器。

形式上，給定同一字母表上的 DFA M1（狀態集 Q1）與 M2（狀態集 Q2），建一台新 DFA，其狀態是所有的對 (p, q)——也就是笛卡兒積 Q1 × Q2。起始狀態是兩個起始狀態組成的對。讀到符號 x 時，這對逐分量移動：從 (p, q) 走到 (delta1(p, x), delta2(q, x))，其中每個 delta 就是那台機器自己的轉移函數。轉移到此已完全固定；「唯一」還要決定的是哪些對是接受的。當「兩半都」接受時讓 (p, q) 接受，就辨識交集；當「任一半」接受時就讓它接受，便辨識聯集。同一套接線，不同的燈號。

M1 = even number of a's        M2 = ends in b
states {E, O}                  states {notB, seenB}
 start E (accept)               start notB (reject)
  E --a--> O   E --b--> E         notB --a--> notB   notB --b--> seenB
  O --a--> E   O --b--> O         seenB --a--> notB  seenB --b--> seenB

PRODUCT  (4 paired states, run both at once):
  state      on a ->        on b ->
  (E,notB)   (O,notB)       (E,seenB)
  (E,seenB)  (O,notB)       (E,seenB)
  (O,notB)   (E,notB)       (O,seenB)
  (O,seenB)  (E,notB)       (O,seenB)
  start = (E,notB)

  INTERSECTION  accept only (E,seenB)   <- even a's AND ends in b
  UNION         accept any pair with E first OR seenB second
一台 DFA、四個成對狀態，並行追蹤兩個條件；只有接受集決定了是聯集還是交集。

這一個構造就證明了對交集「以及」聯集的封閉性，甚至附送一個大小上界：若 M1 有 m 個狀態、M2 有 n 個狀態，則積最多有 m·n 個狀態——丟掉沒有任何輸入能到達的對之後，通常更少。注意它與上一階梯的對比：在那裡，非確定性帶來簡潔，但子集構造的爆炸可能是指數級的。在這裡，讓兩台「確定型」機器並行跑，代價只是它們大小的「乘積」，依然溫和。這個並行追蹤的把戲——同時盯著每個分量——會在你往上爬時一再回來。

翻轉燈號：補集

如果你有一台機器，對「你要的」字串都說「是」，那要怎麼得到一台對「其餘所有」字串說「是」的機器？對 DFA 來說，答案出奇地便宜：把每盞燈都翻轉。原本接受的地方改成拒絕，原本拒絕的地方改成接受。狀態、箭頭、起始狀態——分毫不動。這就是補集構造法的全部：把接受集換成它的反面（新接受集是 Q 減去舊的 F），這台機器現在便辨識補集——也就是原機器拒絕的、Sigma 上的每一個字串。

為什麼翻轉就夠了？因為 DFA 是「完全的」（total）且「確定的」（deterministic）：對任何輸入，它都恰好沿一條路徑走到恰好一個最終狀態，那個狀態若非接受、便是非接受。因此「M 接受 w」與「翻轉後的 M 接受 w」逐字串恰好相反——這正是補集。例子很迷你：一台辨識「偶數個 a」的兩狀態 DFA 在 E 接受、在 O 拒絕；把兩者對調，O 接受、E 拒絕，就得到「奇數個 a」，而箭頭完全相同。

黏接與倒轉：星號、串接、反轉

補集與積都樂於保持確定型，但「黏接類」的運算如果允許自己滑回非確定性，會好論證得多——而你大可這麼做，因為上一階梯已證明每台 NFA 反正都能壓平回 DFA。對串接 LM，拿 L 與 M 的機器把它們縫起來：從 L 機器的每個接受狀態加一條 epsilon 轉移（不讀符號就改變狀態）連到 M 機器的起始狀態，然後只讓 M 的接受狀態接受。直觀上，這台合成機器先讀一個 L 字串，再悄悄跳過去讀一個 M 字串。Kleene 星號 L* 就是同一個把戲變成迴圈。

  1. 對 L*：從 L 的 NFA 出發。加一個全新的起始狀態，並讓它同時是接受狀態（因為 L* 永遠包含空字串 epsilon，也就是「零個拷貝」的情形）。
  2. 從新起始狀態加一條 epsilon 轉移連到舊的起始狀態，讓機器可以選擇性地開始讀一個 L 字串的拷貝。
  3. 從 L 機器的每個接受狀態，加一條 epsilon 轉移繞回舊的起始狀態——這就是那個迴圈，讓你可以再讀一個拷貝、再一個，沒有上限。
  4. 結果是一台辨識 L* 的 NFA；若你想要一台確定型機器，用子集構造法把它轉回 DFA。串接是同樣的做法，只是去掉那條繞回的迴圈、也去掉那個會接受的新起始狀態。

反轉很迷人。要辨識 L 的反轉（每個被接受的字串倒著拼），拿 L 的自動機，然後真的讓它倒著跑：把每條箭頭的方向反過來，讓舊的起始狀態變成新的接受狀態，再加一個新的起始狀態，用 epsilon 移動連到所有舊的接受狀態。反轉箭頭可能製造岔路，所以結果自然是一台 NFA——這沒關係，因為 NFA 與 DFA 識別相同的語言。這三種黏接構造，正是寫一個正規表示式之所以行得通的原因：聯集、串接與星號恰好就是正規表示式的運算子，而 Kleene 定理（來自正規表示式那一階梯）就是那句宏大的斷言——這些構造合起來恰好捕捉了正規語言。

同一個工具箱，反過來用：封閉性作為武器

這裡有個轉折，讓封閉性不只是方便而已。正規語言在這些運算下仍保持正規這件事本身，也是一個證明某語言「不是」正規的辦法——完全不必動用下一篇的幫浦引理。這一招是一種邏輯柔道，叫做把封閉性當作證明工具：先假設你懷疑的語言「是」正規的，用保持正規性的運算把它和「已知是正規」的材料組合起來，如果這個合法的組合落到一個你「早已知道不是正規」的語言上，你就得到矛盾——於是那個懷疑對象從來就不是正規的。

一個做過的例子能讓它具體起來。主張：在 {a, b} 上 a 與 b 個數相等的字串所成的語言 L 不是正規的。為了反證，假設它是。語言 a* b*（先全部是 a、再全部是 b）顯然是正規的。由於正規語言對交集封閉，L 與 a* b* 的交集也會是正規的。但這個交集恰好是 { a^n b^n : n 至少為 0 }——也就是那個著名的語言 a^n b^n。如果你已經信任 a^n b^n 不是正規的（接下來的導覽會把它證得鐵板釘釘），那這就是矛盾：一個正規語言不可能等於一個非正規語言。所以我們唯一做的假設「L 是正規的」必定為假。

對同態的封閉性——一條對符號固定的「尋找並取代」規則，把每個字母換成一個固定字串——又給出另一個切入角：若對你的候選語言施加或反施加一個同態會製造出一個已知非正規的語言，那這個候選語言也不可能是正規的。再配上交集、補集與反轉，這些給了你好幾條獨立的攻擊路線，所以某個能甩開一種封閉性論證的語言，可能會在另一種之下崩潰。

對這件工具的方向要誠實。封閉性論證能證明某語言「非」正規，但永遠不能保證某個給定的語言「是」正規的——對某運算封閉，對一個孤立、單獨存在的語言什麼也沒說。而且這個矛盾的牢固程度，只取決於你的基礎事實：它建立在「早已知道像 a^n b^n 這樣的東西非正規」之上，而那本身又必須靠接下來幾篇裡的幫浦引理或 Myhill-Nerode 定理來掙得。

你現在能做什麼，又指向何方

退一步，數數這篇為你換來了什麼。你現在能用「組合」來設計：分別辨識「合法識別字」與「保留關鍵字」，再取「差集」（與補集取交集）就能辨識「不是關鍵字的識別字」，並且確定地知道結果仍然存在一台單一的有限自動機。你有了明確的食譜——聯集與交集用積、補集用翻燈、串接與星號用 epsilon 縫接、反轉用倒箭頭——而且你理解每一個「為什麼」保持正規性，而不只是死記它會。

但請注意，邊界並沒有移動。封閉性告訴你如何「留在」正規語言家族之內；它無法把 a^n b^n 偷渡進來，因為正規零件的任何有限組合都逃不出家族，而 a^n b^n 從來就不在裡面。那道牆——你兩階梯前認識的有限記憶極限——正是這一整階梯要正面研究的東西。下一篇把鴿籠原理變成幫浦引理，一個檢驗「有限記憶所強迫出現的、無可避免的迴圈」的乾淨測試；再下一篇把它變成證明非正規性的食譜；而收尾的幾篇則交給你那把更鋒利、精確的工具（Myhill-Nerode）與那台唯一最小的機器（DFA 最小化）。你剛建好的這個封閉性工具箱，既是你的施工套件，也是接下來一切的第一件證明武器。