チョムスキー標準形

文脈自由文法(CFG) は書き換え規則の右辺で無制限の記号文字列を持っている.一般的なCFG 構文解析アルゴリズムを表現するのに,制限された「標準形」を書き換え規則に採用するのは有用である.そういった標準形のひとつがチョムスキー標準形である.チョムスキー標準形ではすべてのCFG 生成規則は
\( W_v \rightarrow W_y W_z \) または
\( W_v \rightarrow a \)
の形をしていなければならない.標準形を満さない書き換え規則を,非終端記号をつけ加えて標準形の生成の列に展開することにより,任意のCFG はチョムスキー標準形に改造することができる.従ってチョムスキー標準形のCFGに適用される構文解析アルゴリズムは一般に任意のCFG に適用できる.例えば回文CFG の
\( S \rightarrow aSa \)
という生成規則は
\( S \rightarrow W_1 W_2 \\
W_1 \rightarrow a \\
W_2 \rightarrow SW_1 \)
というチョムスキー標準形に展開することができる.