喬姆斯基正常形式

在形式語言理論中，如果一個無語境語法G的所有生產規則都是這樣的形式，那么它就被稱為喬姆斯基正常形式。A→BC，或A→a，或S→ε。其中，A、B和C是非終端符號，字母a是終端符號（代表一個常量值的符號），S是起始符號，ε表示空字符串。另外，B和C都不可能是起始符號，第三條生產規則只有在ε在L(G)中時才能出現，L(G)是由無語境語法G產生的語言。每一個喬姆斯基正常形式的語法都是無語境的，反之，每一個無語境的語法都可以轉化為一個等價的語法，該語法為喬姆斯基正常形式，其大小不超過原語法大小的平方。

為了將語法轉換為喬姆斯基正常形式，需要按照一定的順序應用一連串的簡單轉換；這在大多數自動機理論的教科書中都有描述。以下每個轉換都建立了喬姆斯基正常形式所需的一個屬性。開始：從右手邊消除開始符號引入一個新的開始符號S0，和一個新的規則S0→S。這不會改變語法的生成語言，而且S0也不會出現在任何規則的右側。術語：消除具有非孤島終端的規則為了消除每條規則A→X1...a...Xn的每個規則，其終端符號a不是右側的xxx符號，為每個這樣的終端引入一個新的非終端符號Na，和一個新的規則如果右側出現幾個終端符號，同時用相關的非終端符號替換每個終端符號。這不會改變語法的生成語言。

BIN：消除右手邊有2個以上的非終端符號替換每個規則要消除這種形式的所有規則，首先要確定衍生出ε的所有非終結符的集合。如果一個規則A→ε存在，那么A就是可空的。如果一個規則A→X1......獲得一個中間語法，將每個規則替換為A→X1...Xn通過刪除這個語法中的每條ε規則，除非其左側是起始符號，否則就得到了轉換后的語法。例如，在下面的語法中，起始符號為S0。S0→AbB|CB→AA|ACC→b|cA→a|ε除非這是一條已經（或正在）被刪除的單元規則。由于B是非終端符號A的單元閉合的成員，因此在結果語法中跳過非終端符號B是可能的。

在選擇上述變換的應用順序時，必須考慮到一些變換可能會破壞其他變換所取得的結果。例如，如果START在UNIT之后應用，就會重新引入一個單位規則。該表顯示了哪些順序是被允許的。此外，語法大小的最壞情況下的膨脹取決于轉換順序。用|G|表示原始語法G的大小，最壞情況下的大小膨脹可能在|G|2到22|G|之間，這取決于使用的轉換算法。語法大小的膨脹取決于DEL和BIN之間的順序。當DEL首先完成時，它可能是指數級的，但在其他情況下是線性的。