チョムスキー標準形
言語の理論(形式言語の理論)において、次のような生成規則のみからなる文法をチョムスキー標準形(チョムスキーひょうじゅんけい)という。
A → B C {\displaystyle A\rightarrow BC} または
A → α {\displaystyle A\rightarrow \alpha } または
S → ε {\displaystyle S\rightarrow \varepsilon }
ここで、A 、 B および C は非終端記号、α は終端記号であり、Sは開始記号を表し、ε は空列を表すものとする。
また、チョムスキー標準形には次のような性質が挙げられる。
チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書き換えることができる。