チョムスキー階層とは

チョムスキーが、機械的に文章を解釈するために作ったルール

以下、左生成のルール（文字は左から読むという習慣に合わせている）

下にあるものは上のものを内包する（例えば文脈自由文法や文脈依存文法は正規文法を内包する）

a、b: 終端記号 W: 非終端記号

• 正規文法 W→aWとW→aのみ許される

• 文脈自由文法 任意のW→bのみ許される

• 文脈依存文法 非終端記号の変形は前後の文脈に依存。 生成規則はa1Wa2→a1ba2

• 区構造文法 任意の生成規則が許される。何でもあり

オートマトンとの関連

チョムスキー階層のそれぞれの文法はオートマトンに対応している。

• 文法 構文解析状態オートマトン
• 正規文法 有限状態オートマトン
• 文脈自由文法 プッシュダウンオートマトン
• 文脈依存文法 線形有界オートマトン
• 句構造文法 チューリング機械