チョムスキー階層

formal-languageautomata-theorycomputer-science

形式言語を生成する形式文法の包含階層。1956年にノーム・チョムスキーが発表。

形式文法 = 文字列の生成ルール

「ある文字列がこの言語に属するか？」を判定する仕組み。プログラマ向けに言えば、バリデーション関数の表現力の分類。

// 形式文法を TypeScript で表現するとこうなる
type Grammar = {
  nonTerminals: string[];   // N: まだ展開できる記号（変数みたいなもの）
  terminals: string[];      // Σ: 最終的な出力文字（リテラルみたいなもの）
  rules: Rule[];            // P: 展開ルール
  start: string;            // S: 最初の記号
};
type Rule = { from: string; to: string };

// 例: a が n 個、b が n 個 並ぶ文字列（ab, aabb, aaabbb, ...）
const grammar: Grammar = {
  nonTerminals: ["S"],
  terminals: ["a", "b"],
  rules: [
    { from: "S", to: "aSb" },  // S を aSb に展開できる
    { from: "S", to: "ab" },   // S を ab に展開できる
  ],
  start: "S",
};
// S → aSb → aaSbb → aaabbb  （S を繰り返し展開して文字列を生成）

階層 = 「バリデーション関数にどれだけの道具を許すか」

// Type 3: 変数1個で足りる（状態だけ、メモリなし）
function type3(input: string): boolean {
  let state = "start";
  for (const ch of input) {
    // 今の状態と文字だけで次の状態が決まる
    state = transition(state, ch);
  }
  return state === "accept";
}

// Type 2: スタック（配列の push/pop）が必要
function type2(input: string): boolean {
  const stack: string[] = [];
  for (const ch of input) {
    // 今の状態 + スタックのトップ で判断
  }
  return stack.length === 0;
}

// Type 1: メモリは使えるが入力長に比例する量まで
function type1(input: string): boolean {
  const memory = new Array(input.length * C); // 定数倍まで
  // ...
}

// Type 0: 何でもあり = 普通のプログラム
function type0(input: string): boolean {
  // 任意のコードが書ける。ただし停止しないかもしれない
}

階層の対応表

Typeプログラマの感覚使える道具身近な例
Type 3正規表現変数1個（状態）/^a*b$/
Type 2再帰 / スタックstack.push() / stack.pop()括弧の対応チェック
Type 1配列を使った検証入力長に比例するメモリ型チェック
Type 0任意のプログラム制限なし停止問題

文法 ⇔ 認識オートマトン対応表

階層の本質は「生成する文法」と「受理するオートマトン（≒メモリの形）」がぴったり対応している点にある。文法の生成規則に課す制約が、それを認識するのに必要な計算資源を決める。

Type文法（生成規則の形）認識オートマトンメモリの形言語クラス例
Type 0句構造文法（α → β、制約なし）チューリング機械（TM）無制限テープ帰納的可算言語停止問題、任意計算
Type 1文脈依存文法（αAβ → αγβ、長さ非短縮）線形有界オートマトン（LBA）入力長に比例するテープ文脈依存言語aⁿbⁿcⁿ、型チェック
Type 2文脈自由文法（A → γ、左辺は非終端1個）プッシュダウン・オートマトン（PDA）スタック1本文脈自由言語aⁿbⁿ、括弧の対応、JSON
Type 3正規文法（A → aB / A → a、線形）有限オートマトン（DFA/NFA）状態のみ（メモリなし）正規言語a*b、トークン分割

対応の読み方：規則の左辺をどこまで複雑にできるか = 必要なメモリの形。左辺が1記号（Type 2/3）ならスタックや状態で足り、左辺に文脈（周囲の記号）が必要（Type 1）ならテープ全体が要る。決定性 PDA は文脈自由言語の真部分（LR 文法）しか受理できず、ここで非決定性が本質的になる点も実務上重要。

包含関係

Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0

正規表現で書けるものは、再帰でも書ける。逆は無理。
再帰で書けるものは、配列でも書ける。逆は無理。

各包含は真の包含。aⁿbⁿ（対応した括弧）は Type 2 だが Type 3 では書けず（有限状態では数を覚えられない＝反復補題で証明）、aⁿbⁿcⁿ（3つの数を揃える）は Type 1 だが Type 2 では書けない（スタック1本では2つの計数を同時に保てない）。

なぜプログラマに関係あるか

押さえどころ（カード化候補）

関連

Graph

Backlinks