上下文無關語言:化簡與正規形式

移除 ε-產生式(removing epsilon-productions)

假設一張表單有個可填可不填的中間名欄位。與其隨身帶著一個特別的「空白」標記,不如直接印兩種版本的表單:一種有這欄、一種沒有。移除 ε-產生式對文法做的正是這件事:與其讓變數在推導時消失,不如把「出現」與「缺席」兩種選擇直接烤進其他規則裡,這樣就沒有任何規則需要推導出空字串。

步驟有兩個階段。第一,找出所有可空變數(nullable variable):若 A 能推導出空字串 epsilon,無論是直接(A -> epsilon)還是間接(A -> BC 而 B 與 C 皆可空),則 A 是可空的。第二,對每條規則,產生涵蓋其右側可空變數各種刪法的新版本。例如若 A 可空、且有規則 S -> AbA,你就加入每個 A 出現或省略的版本:S -> AbA | bA | Ab | b。然後刪掉所有 A -> epsilon 規則。新文法在沒有任何 ε-產生式的情況下,推導出完全相同的非空字串。

有一個例外值得明說:若原語言本身含有空字串(起始符號可空),你無法移除這件事。標準做法是新增一個全新的起始符號 S0,加上唯一的規則 S0 -> S | epsilon,把 S0 -> epsilon 保留為唯一允許的 ε-產生式,並確保 S0 從不出現在任何右側。移除 ε-產生式是通往喬姆斯基正規形式的第一個清理步驟,而它可能使規則數倍增——若一條規則裡出現 k 個可空變數,這條規則可能衍生出多達 2^k 個版本,這是膨脹的真正來源之一。

由 S -> AB, A -> aA | epsilon, B -> b:A 可空。加入把 A 刪掉的 S 版本:S -> AB | B。刪除 A -> epsilon,並把 A -> aA 換成 A -> aA | a。結果:S -> AB | B, A -> aA | a, B -> b——沒有 epsilon,字串相同(ab、aab、b……)。

每個可空變數都被「就地展開」成出現或缺席兩種情形,併入提到它的規則中。

若某條規則的右側整個可空,不要加入把一切都刪到只剩 epsilon 的版本(那會重新引入 ε-產生式)。唯一能留下的 ε-規則(若需要)是新起始符號上的 S0 -> epsilon。

又稱
epsilon eliminationnull-production removalepsilon-free grammarε-產生式消除ε-free 文法