チョムスキー階層とは（全体像）
チョムスキー階層は、言語（＝決まったルールに従う文字列の集まり）を、表現できる力の強さで4つに分類した体系のこと。「どんな複雑なパターンまで表せるか」で、Type 0（最強）からType 3（最も制限的）まで段階づけられている。
大事なのは、上位が下位を含むこと（Type 0 ⊃ Type 1 ⊃ Type 2 ⊃ Type 3）。上ほど表現力が高いが、そのぶん実装（扱うこと）が難しくなる。
身近な対応で押さえると速い。
- Type 3（正規） … 正規表現。いちばん簡単で、有限オートマトンで扱える。
- Type 2（文脈自由） … プログラミング言語の構文。BNFで書ける。
- Type 0（句構造） … 制限なしの最強。チューリング機械で扱う。
詳しく：4段階と対応する機械だけ覚えれば戦える
ここが記事の心臓部。4段階を、対応する機械と例で整理する。
チョムスキー階層の4段階
| Type | 文法 | 対応する機械 | 例 |
|---|---|---|---|
| Type 0 | 句構造文法 | チューリング機械 | 制限なし（最強） |
| Type 1 | 文脈依存文法 | 線形拘束オートマトン | 自然言語の一部 |
| Type 2 | 文脈自由文法（CFG） | プッシュダウンオートマトン | プログラミング言語の構文 |
| Type 3 | 正規文法 | 有限オートマトン | 正規表現（最も制限的） |
いちばん試験に出るのが、Type 2（文脈自由文法・CFG）＝プログラミング言語の構文、Type 3（正規文法）＝正規表現という対応だ。括弧の対応（開いた数だけ閉じる）のようなパターンは正規表現（Type 3）では表せず、Type 2（文脈自由）が必要——つまりCFGのほうが正規表現より強力だ。
覚えておきたい対応
| 段階 | 表すもの |
|---|---|
| Type 2（文脈自由） | プログラミング言語の構文・BNFで記述 |
| Type 3（正規） | 正規表現・有限オートマトン |
なお、上位ほど強力だが実装は難しい。最強のType 0は、停止するかどうかの判定すらできない（停止性問題）ほど扱いが難しい。
わかりやすく言い換えると
要するに、チョムスキー階層は「言語を難しさで4段階に分けたレベル表」だ。
①Type 3（正規） … いちばん簡単なレベル。正規表現で表せる単純なパターン
②Type 2（文脈自由） … プログラミング言語のレベル。括弧の対応のような入れ子も表せる
③Type 0（句構造） … 最強だが、扱いがとても難しいレベル
ゲームの難易度のように、上に行くほど「表せること」は増えるが、コンピュータで「扱うこと」は難しくなる。だから実用では、必要十分なレベル（言語の構文ならType 2）を選ぶ、というわけだ。
試験のツボ
🔴 一番出る：段階と対応する機械
①Type 3＝正規文法＝有限オートマトン＝正規表現
②Type 2＝文脈自由文法（CFG）＝プログラミング言語の構文
③Type 0＝句構造文法＝チューリング機械（最強）
🔴 次に出る：CFGと正規表現の強さの違い
①CFG（Type 2）は正規表現（Type 3）より強力
②括弧の対応のような入れ子はType 2が必要
🟡 押さえると安定：包含関係と難しさ
①Type 0 ⊃ Type 1 ⊃ Type 2 ⊃ Type 3
②上ほど表現力が高いが実装は難しい
よくある間違い
①「すべての言語はType 0で、4段階に分ける意味はない」→ ✗ 表現力に差があり、4段階に分類される。
②「文脈自由文法（CFG）と正規表現はまったく同じ強さである」→ ✗ CFG（Type 2）のほうが強力。括弧の対応などは正規表現では表せない。
③「プログラミング言語の構文はType 3（正規）で表せる」→ ✗ プログラミング言語の構文はType 2（文脈自由・CFG）。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（段階と機械）
チョムスキー階層に関する次の記述のうち、正しいものはどれか。
- Type 3（正規）はチューリング機械で認識する、最も表現力の高い段階だとされている
- Type 0（句構造）は有限オートマトンで認識する、最も制限的な段階である
- すべての段階が同じ表現力を持ち、対応する機械にも違いはないとされている
- Type 3は正規文法で有限オートマトン、Type 0は句構造文法でチューリング機械
解答は 4 だぜ。
Type 3は正規文法（有限オートマトン）、Type 0は句構造文法（チューリング機械）だ。Type 3が最も制限的、Type 0が最強、と押さえとけ。
選択肢1はType 3を「最強・チューリング機械」とする誤り。選択肢2はType 0を「有限オートマトン・最も制限的」とする誤り。選択肢3は「すべて同じ表現力」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | Type 3は最も制限的・有限オートマトン |
| 2 | ✗ | Type 0は最強・チューリング機械 |
| 3 | ✗ | 段階で表現力が異なる |
| 4 | ✓ | Type 3＝有限オートマトン・Type 0＝TM |
オリジナル問題2（CFGと正規表現）
文脈自由文法（CFG）と正規表現の関係に関する次の記述のうち、正しいものはどれか。
- 正規表現のほうがCFGよりずっと強力で、括弧の対応もすべて表せるものとされている
- CFG（Type 2）は正規表現（Type 3）より強力で、括弧の対応も表せる
- CFGと正規表現はまったく同じ強さで、表せる範囲に違いはないとされる
- CFGは正規表現より制限的で、単純なパターンしか表せないものである
解答は 2 だぜ。
CFG（Type 2）は正規表現（Type 3）より強力で、括弧の対応（開いた数だけ閉じる）のような入れ子も表せる。これが正規表現では表せない部分だな。
選択肢1は「正規表現のほうが強力」が逆。選択肢3は「同じ強さ」が誤り。選択肢4は「CFGのほうが制限的」が逆だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 強いのはCFGのほう |
| 2 | ✓ | CFGは正規表現より強力 |
| 3 | ✗ | 強さに違いがある |
| 4 | ✗ | CFGのほうが強力 |
オリジナル問題3（プログラミング言語の位置）
プログラミング言語の構文の位置づけに関する次の記述のうち、正しいものはどれか。
- プログラミング言語の構文はType 3（正規）にあたり、正規表現だけで表せるとされている
- プログラミング言語の構文はType 0で、停止性すら判定できない段階にあたる
- プログラミング言語の構文は主にType 2（文脈自由・CFG）で、BNFで記述できる
- プログラミング言語の構文は階層に当てはまらず、分類できないものである
解答は 3 だぜ。
プログラミング言語の構文は主にType 2（文脈自由文法・CFG）で、BNFで書ける。括弧の入れ子などを扱えるから、正規表現（Type 3）では足りないんだ。
選択肢1は「Type 3・正規表現だけ」が誤り。選択肢2は「Type 0」とする誤り。選択肢4は「分類できない」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | Type 3では表せない |
| 2 | ✗ | Type 0ではなくType 2 |
| 3 | ✓ | Type 2（CFG）・BNFで記述 |
| 4 | ✗ | Type 2に分類される |
まとめ
押さえどころ
- 🔴 4段階と機械 ＝ Type 3（正規・有限オートマトン）／Type 2（文脈自由・CFG）／Type 0（句構造・チューリング機械）。
- 🔴 CFGと正規表現 ＝ CFG（Type 2）のほうが強力。括弧の対応はType 2が必要。
- 🟡 位置づけ ＝ プログラミング言語の構文はType 2。正規表現はType 3。上ほど強力だが実装は難しい。
次に学ぶ
- 有限オートマトン（DFA・NFA） ── Type 3（正規言語）に対応する機械。階層のいちばん下を支えるしくみが分かる。
- 構文解析（LL・LR） ── Type 2（文脈自由文法）を実際に処理する技術。階層の理論が実務につながる。
執筆: SikakuQuest編集部