チョムスキー階層における言語のクラスの包含関係として、正しいものはどれか。ここで、⊊ は真部分集合を表す。

解説

正解は「正規言語 ⊊ 文脈自由言語 ⊊ 文脈依存言語 ⊊ 句構造言語」です。チョムスキー階層は、生成規則の制限の強さで文法を3型（正規）、2型（文脈自由）、1型（文脈依存）、0型（句構造）に分類したもので、制限が緩いほど生成できる言語のクラスが大きくなります。対応する計算モデルは、有限オートマトン、非決定性プッシュダウンオートマトン、線形有界オートマトン、チューリング機械です。「文脈自由言語 ⊊ 正規言語 ⊊ …」は最初の2つが逆です。「正規言語 ⊊ 文脈依存言語 ⊊ 文脈自由言語 ⊊ …」は中の2つが逆です。「正規言語 = 文脈自由言語 ⊊ …」は、$\{a^n{b}^n\}$ のように文脈自由だが正規でない言語があるため誤りです。