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

為何需要正規形式(normal forms)

想像有人遞給你一本厚厚的食譜,每位廚師都用自己的風格寫:一個說「加一撮鹽」,另一個寫化學式,第三個畫圖。若要造一台能自動照任何食譜操作的機器,你會先把它們全部改寫成同一個死板的範本:每一行剛好是對至多兩種食材的一個動作。菜餚做出來還是一樣,但現在簡單的機器讀得懂了。文法的正規形式正是這種範本:一個固定、可預測的形狀,每條規則都必須套進去。

上下文無關文法(context-free grammar, CFG)是一組像 A -> aB 或 S -> AB | a 這樣的規則,其中大寫字母是可以繼續改寫的變數(非終端符號),小寫字母是不能再改寫的終端符號。在原始狀態下,文法允許幾乎任何形狀的規則,對人方便,對機器和證明卻很糟。正規形式限制允許的規則形狀,使每條規則長得一樣。兩個著名的形式是喬姆斯基正規形式(Chomsky normal form, CNF),其每條規則為 A -> BC 或 A -> a;以及 Greibach 正規形式(Greibach normal form, GNF),其每條規則以終端符號開頭,A -> a alpha。關鍵事實是:每個 CFG 都能改寫成這些形式而產生完全相同的語言(空字串另行處理除外)。

正規形式之所以存在,是因為一致的形狀讓機械化推理成為可能。CNF 整齊的二元分支剖析樹,正是 CYK 演算法能以 O(n^3) 時間填表的關鍵,也讓上下文無關幫浦引理與許多歸納證明乾淨地走通。GNF 保證每一步推導都消耗一個終端符號,從而限制推導長度,並通向預測式剖析與一個簡潔的下推自動機構造。誠實的代價是:轉換可能讓文法變大,而且會改變剖析樹,因此附在原規則上的語意必須事後重新接上。

同一個語言 {a^n b^n : n >= 1} 可以雜亂地寫成 S -> aSb | ab,也可以用 CNF 寫成 S -> AX, X -> SB, S -> AB, A -> a, B -> b。兩者都恰好產生 aabb、aaabbb 等等;只有後者符合機器能逐一處理的統一範本。

同一語言,兩種形狀:正規形式以人類可讀性換取機器友善的一致性。

正規形式不會讓文法的表達能力變強:它產生的仍是上下文無關語言,不多也不少。它只是把規則的形狀標準化。

又称
standard formcanonical grammar shape正規形式標準形式