チョムスキー標準形

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

A → B C {\displaystyle A\rightarrow BC} または
A → α {\displaystyle A\rightarrow \alpha } または
S → ε {\displaystyle S\rightarrow \varepsilon }

ここで、 A {\displaystyle A} 、 B {\displaystyle B} および C {\displaystyle C} は非終端記号、 α {\displaystyle \alpha } は終端記号であり、 S {\displaystyle S} は開始記号を表し、 ε {\displaystyle \varepsilon } は空列を表すものとする。

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

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

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

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

関連項目