チョムスキー階層：形式文法と言語の4分類

水準と特徴

階層には、最も制約が少ない0から最も制約が多い3まで、4つの型がある。番号が大きい型は、より小さい番号の型の制約をすべて満たしつつ、生成規則の形式に追加の要件を課す。

• 0型（無制限文法）：左辺が空でない限り、生成規則は任意の形式をとれる。再帰的可算言語を生成し、チューリング機械によって認識される。
• 1型（文脈依存文法）：生成規則は長さを減少させず、周囲の記号に依存しうる。その言語は線形有界オートマトンによって認識される。
• 2型（文脈自由文法）：各生成規則は、単一の非終端記号を終端記号と非終端記号からなる文字列へ置き換える。文脈自由言語を生成し、プッシュダウン・オートマトンに対応する。
• 3型（正規文法）：生成規則は強く制限され、通常は右線形または左線形である。有限オートマトンで認識され、正規表現で記述される正規言語を生成する。

歴史と発展

チョムスキーは、自然言語における統語記述の諸側面を形式化し、言語理論を新たに生まれた計算モデルと結び付ける試みの一環として、この分類を提案した。時とともに階層は理論計算機科学の中心的概念となり、文法の形式、オートマトンのモデル、決定可能性や計算量の性質を明確に結び付けるものとなった。

用途と例

この階層は実践的・理論的研究を導く。正規言語と文脈自由言語は、コンパイラにおける字句解析やプログラミング言語の構文の基礎をなす。一方、文脈依存および無制限のクラスは、高度な言語モデリング、形式検証、計算可能性の研究で現れる。例として、トークンのパターンには正規表現が、対応する括弧のような入れ子構造には文脈自由文法が用いられる。

主な性質と区別

3型 ⊂ 2型 ⊂ 1型 ⊂ 0型という包含関係は基本的である。通常の無限言語の設定では、各クラスは次に大きいクラスに真に包含される。クラスごとに閉包性や決定問題も異なり、たとえば空性や所属判定の問合せでは計算量に差がある。この階層は、文法形式とオートマトンモデルの表現力を比較するための簡潔な方法として、現在も用いられている。