チョムスキー標準形
出典: フリー百科事典『ウィキペディア（Wikipedia）』
計算機科学における形式文法で、次のような生成規則のみからなる文法をチョムスキー標準形という。
または
または
ここで、A 、 B および C は非終端記号、α は 終端記号であり、Sは開始記号を表し、ε は空列を表すものとする。
また、チョムスキー標準形には次のような性質が挙げられる。
- チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書換えることができる。
- S→ε型の規則(空列を導出する文法に含まれる)を除いて、チョムスキー標準形の文法における全ての生成規則は拡張的である。つまり、終端記号と非終端記号からなる文字列に生成規則を適用して生成される文字列の長さは元の文字列の長さよりも等しいか、あるいは長くなる。
- 長さ n の文字列を導出するには、2n-1 回以上規則を適用する必要がある。
- 1つの非終端記号から導出される非終端記号は常に2つとなり、構文木は二分木で表されるため、木の深さは最大でも文字列の長さである。
これらの性質から、言語理論や計算複雑性理論の分野における証明では、しばしばチョムスキー標準形が用いられる。また、CYKアルゴリズム(チョムスキー標準形の文法が与えられた文字列を生成できるか否かを決定するアルゴリズム)のように、様々な効率的なアルゴリズムの基礎となっている。
チョムスキー標準形の名前は、チョムスキー階層を発表した米国の言語学者ノーム・チョムスキーにちなんで名付けられたものである。
