喬姆斯基正規形式（Chomsky normal form）
/ Chomsky: CHOM-skee /
想像強迫家譜中每個分叉都剛好是一位家長帶兩個孩子，每片葉子都是一個具名的人。樹可能變高，你可能得發明幾個輔助節點，但它的形狀變得極其規則——而任何你想在它上面計算的東西（計數、配對、搜尋）都成了在左子與右子上的乾淨遞迴。喬姆斯基正規形式（Chomsky normal form, CNF）對文法做的正是這件事：它把每條規則逼成兩種死板形狀之一，使剖析樹永遠是二元的。
若文法每條規則都恰為兩種形式之一：A -> BC（一個變數改寫成恰好兩個變數）或 A -> a（一個變數改寫成單一終端符號），則該文法處於 CNF。唯一允許的例外是起始符號上的 S -> epsilon，僅用於讓語言能包含空字串。每個上下文無關文法都能轉成 CNF。這個構造在化簡之後進行（移除 epsilon、單位、無用符號），然後做兩個塑形步驟：把每個位於較長規則內部的終端符號換成新變數（例如把 A -> bC 改成 A -> B' C 並加上 B' -> b），以及把每條長度超過兩個符號的右側拆成一串二元規則（把 A -> XYZ 改成 A -> X T 並加上 T -> YZ）。結果產生相同語言，且只有二元或終端規則。
CNF 受重視，是因為二元分支的剖析樹給演算法一個乾淨的形狀。CYK 剖析演算法之所以是在子字串上的動態規劃，正是因為在 CNF 中一個子字串被剖析為 A -> BC，其中 B 涵蓋前綴、C 涵蓋其餘，從而填出一張 O(n^3) 的表。CNF 也是上下文無關幫浦引理與許多結構歸納證明的基礎，在那裡固定的分支因子讓案例分析得以控制。誠實的告誡：轉換可能讓文法變大（通常是常數倍或溫和的多項式倍），而且會改變剖析樹，因此附在原規則上的語意動作必須重新接到新規則上。
轉換 S -> aSb | ab：內部的終端符號需要輔助變數 A -> a、B -> b，第一條規則變成 S -> A S'（S' -> S B），第二條變成 S -> A B。最終 CNF：S -> AX | AB, X -> SB, A -> a, B -> b。現在每條規則都是 A->BC 或 A->a，而 aabb 仍可推導為 S => AX => A SB => A AB B => aabb。
先把內部終端符號換成變數，再把長右側拆成二元規則。
CNF 不會讓文法更強大——它描述的仍是上下文無關語言。唯一允許的 ε-規則 S -> epsilon 只是為了讓含空字串的語言能被表達；其他任何規則都不可推導出 epsilon。