チョムスキー標準形のソースを表示

言語の理論（[[形式言語]]の理論）において、次のような[[形式文法#生成文法|生成規則]]のみからなる文法を'''チョムスキー標準形'''（チョムスキーひょうじゅんけい）という。

:<math> A \rightarrow BC </math> または
:<math> A \rightarrow \alpha</math> または
:<math> S \rightarrow \varepsilon </math>

ここで、<math>A</math>、<math>B</math> および <math>C</math> は[[非終端記号]]、<math>\alpha</math> は[[終端記号]]であり、<math>S</math> は開始記号を表し、<math>\varepsilon</math> は空列を表すものとする。

また、チョムスキー標準形には次のような性質が挙げられる。

* チョムスキー標準形で表すことのできる文法は全て[[文脈自由文法|文脈自由]]であり、また全ての[[文脈自由文法]]は、これと等価なチョムスキー標準形の文法に書き換えることができる。
* <math> S \rightarrow \varepsilon </math> 型の規則（空列を導出する文法に含まれる）を除いて、チョムスキー標準形の文法における全ての生成規則は拡張的である。つまり、終端記号と非終端記号からなる文字列に生成規則を適用して生成される文字列の長さは元の文字列の長さよりも等しいか、あるいは長くなる。
* 長さ <math> n </math> の文字列を導出するには、<math> 2n-1 </math> 回以上規則を適用する必要がある。
* 1つの非終端記号から導出される非終端記号は常に2つとなり、[[構文木]]は[[二分木]]で表されるため、木の深さは最大でも文字列の長さである。

これらの性質から、[[言語理論]]や[[計算複雑性理論]]の分野における証明では、しばしばチョムスキー標準形が用いられる。また、[[CYKアルゴリズム]]（チョムスキー標準形の文法が与えられた文字列を生成できるか否かを決定するアルゴリズム）のように、様々な効率的な[[アルゴリズム]]の基礎となっている。

チョムスキー標準形の名前は[[ノーム・チョムスキー]]にちなむ。

== 関連項目 ==
* [[文脈自由文法]]
* [[バッカス・ナウア記法]]
* [[グライバッハ標準形]]

{{DEFAULTSORT:ちよむすきひようしゆんけい}}
[[Category:形式言語]]
[[Category:生成文法]]
[[Category:数学に関する記事]]
[[Category:ノーム・チョムスキー]]