第3章 形式言語とオートマトン理論

はじめに

形式言語理論は、プログラミング言語の構文解析、コンパイラ設計、文字列処理アルゴリズムなど、コンピュータサイエンスの多くの分野で基礎となる理論です。本章では、言語を認識する計算モデルであるオートマトンを、その計算能力に応じて階層的に学びます。

有限オートマトンから始まり、より強力なプッシュダウンオートマトンへと進むことで、計算モデルの能力と限界を体系的に理解します。各モデルが認識できる言語クラス（正規言語、文脈自由言語）の性質を詳しく調べ、実用的な応用への橋渡しをします。

通し例: 安全なメッセージ配送基盤 入力メッセージの形式検査、配送コマンドの構文、ルーティング規則の前処理は、正規言語や文脈自由言語として切り出すと整理しやすくなります。本章では、その入口として「どの文字列を許すか」を機械で表す見方を獲得します。

学習目標

• 正規言語・文脈自由言語（CFL）の定義と基本性質を説明できる
• DFA/NFA/ε-NFA の定義を述べ、NFA と DFA の等価性を証明できる
• 正規表現から NFA への Thompson 構成と DFA 最小化の流れを説明できる
• ポンピング補題や Myhill–Nerode により非正規性を示せる
• PDA と CFG の対応関係（等価性）を概説できる

3.1 形式言語

3.1.1 基本定義

定義 3.1 アルファベット（alphabet）Σ は、記号の空でない有限集合である。

例

• \(\Sigma_1 = \{0, 1\}\)（2進アルファベット）
• \(\Sigma_2 = \{a, b, c, \ldots, z\}\)（英小文字）
• \(\Sigma_3 = \{0, 1, \ldots, 9, +, -, \times, \div, (, )\}\)（算術式の記号）

定義 3.2 Σ 上の文字列（string）は、Σ の要素の有限列である。長さ 0 の文字列を空文字列（empty string）と呼び、ε で表す。

記法

• \(\lvert w\rvert\)：文字列 w の長さ
• \(w_i\)：w の i 番目の文字（\(1 \le i \le \lvert w\rvert\)）
• \(\Sigma^{\ast}\)：Σ 上のすべての文字列の集合
• \(\Sigma^+\)：Σ 上の空でない文字列の集合（\(\Sigma^+ = \Sigma^{\ast} \setminus \{\epsilon\}\)）
• \(\Sigma^n\)：長さ n の文字列の集合

定義 3.3 Σ 上の言語（language）は、\(\Sigma^{\ast}\) の部分集合である。

3.1.2 文字列の演算

定義 3.4 文字列の基本演算は次のとおりである。

1. 連結（concatenation）：文字列 x, y の連結 xy は、x の後に y を続けた文字列（加算や集合和を表す + 記号とは混同しない）
   • 性質：\(\lvert xy\rvert = \lvert x\rvert + \lvert y\rvert\)
   • 単位元：xε = εx = x
2. 冪乗：\(w^n = ww\cdots w\)（n 個の w の連結）
   • \(w^0 = \epsilon\)
   • \(w^{n+1} = w^n w\)
3. 逆転（reversal）：\(w = a_1a_2\cdots a_n\) の逆転 \(w^R = a_n\cdots a_2a_1\)
   • \(\epsilon^R = \epsilon\)
   • \((xy)^R = y^R x^R\)
4. 部分文字列：v が w の部分文字列 ⟺ \(\exists x, y \in \Sigma^{\ast},\ w = xvy\)
   • 接頭辞（prefix）：w = xv となる x
   • 接尾辞（suffix）：w = vx となる x

3.1.3 言語の演算

定義 3.5 言語 \(L_1, L_2 \subseteq \Sigma^{\ast}\) に対する演算は次のとおりである。

1. 和集合：\(L_1 \cup L_2 = \{w \mid w \in L_1 \lor w \in L_2\}\)
2. 共通部分（intersection）：\(L_1 \cap L_2 = \{w \mid w \in L_1 \land w \in L_2\}\)
3. 補集合：\(\overline{L} = \Sigma^{\ast} \setminus L\)
4. 連結：\(L_1L_2 = \{xy \mid x \in L_1 \land y \in L_2\}\)
5. 冪乗
   • \(L^0 = \{\epsilon\}\)
   • \(L^{n+1} = L^n L\)
6. クリーネ閉包：\(L^{\ast} = \bigcup_{n=0}^{\infty} L^n\)
7. 正閉包：\(L^+ = \bigcup_{n=1}^{\infty} L^n\)

例 3.1 L = {0, 11} のとき、次のとおりである。

• \(L^2 = \{00, 011, 110, 1111\}\)
• \(L^{\ast} = \{\epsilon, 0, 11, 00, 011, 110, 1111, \ldots\}\)

3.1.4 形式言語の実用的応用

計算機科学における形式言語の応用

1. プログラミング言語の設計
   • 字句解析：正規表現によるトークン識別
   • 構文解析：文脈自由文法による構文構造の解析
   • 意味解析：属性文法による型検査と意味規則
2. 文字列処理と検索
   • 正規表現エンジン：パターンマッチングとテキスト処理
   • データベース検索：クエリ言語の解析
   • バイオインフォマティクス：DNA配列のパターン検索
3. ネットワークとセキュリティ
   • プロトコル仕様：通信プロトコルの状態遷移
   • ファイアウォール：パケットフィルタリングルール
   • ウイルス検出：マルウェアの署名パターン

具体例：メールアドレスの検証

# 正規表現による形式検証
import re

def validate_email(email):
    # 簡略化されたメールアドレスのパターン
    pattern = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
    return bool(re.match(pattern, email))

# 対応する形式言語
# L_email = {文字列 w | w は有効なメールアドレス形式}
# 
# この言語は以下の形式で表現できる：
# L_email = L_local @ L_domain . L_tld
# 
# ここで：
# - L_local: ローカル部分の文字列集合
# - L_domain: ドメイン部分の文字列集合  
# - L_tld: トップレベルドメインの文字列集合

プログラミング言語での字句解析例

# Python風の字句解析器の概念
class Token:
    def __init__(self, type, value, line, column):
        self.type = type
        self.value = value
        self.line = line
        self.column = column

# 各トークンに対応する正規表現
token_patterns = {
    'NUMBER': r'\d+(\.\d+)?',           # 数値
    'IDENTIFIER': r'[a-zA-Z_][a-zA-Z0-9_]*',  # 識別子
    'KEYWORD': r'(if|else|while|for|def|return)',  # キーワード
    'OPERATOR': r'[+\-*/=<>!]+',        # 演算子
    'DELIMITER': r'[(){}[\],;:]',       # 区切り文字
    'WHITESPACE': r'\s+',               # 空白
    'COMMENT': r'#.*',                  # コメント
}

# 対応する形式言語
# L_program = (L_number ∪ L_identifier ∪ L_keyword ∪ L_operator ∪ L_delimiter ∪ L_whitespace ∪ L_comment)*

3.2 有限オートマトン

3.2.1 決定性有限オートマトン（DFA）

定義 3.6 決定性有限オートマトン（Deterministic Finite Automaton, DFA）は5つ組 \(M = (Q, \Sigma, \delta, q_0, F)\) である。ここで、次のとおりとする。

• \(Q\)：状態の有限集合
• \(\Sigma\)：入力アルファベット
• \(\delta: Q \times \Sigma \to Q\)：遷移関数
• \(q_0 \in Q\)：初期状態
• \(F \subseteq Q\)：受理状態の集合

定義 3.7 DFA M の拡張遷移関数 \(\hat{\delta}: Q \times \Sigma^{\ast} \to Q\) を帰納的に定義する。

• \(\hat{\delta}(q, \epsilon) = q\)
• \(\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)\)（\(w \in \Sigma^{\ast}, a \in \Sigma\)）

定義 3.8 DFA \(M\) が文字列 \(w\) を受理するとは、\(\hat{\delta}(q_0, w) \in F\) であること。

M が認識する言語：\(L(M) = \{w \in \Sigma^{\ast} \mid \hat{\delta}(q_0, w) \in F\}\)

例 3.2 0 の個数が偶数である2進文字列を認識する DFA

\(M = (\{q_0, q_1\}, \{0, 1\}, \delta, q_0, \{q_0\})\)。ここで：

• \(\delta(q_0, 0) = q_1, \delta(q_0, 1) = q_0\)
• \(\delta(q_1, 0) = q_0, \delta(q_1, 1) = q_1\)

状態の意味

• \(q_0\)：これまでに読んだ0の個数が偶数（受理状態）
• \(q_1\)：これまでに読んだ0の個数が奇数

3.2.2 非決定性有限オートマトン（NFA）

定義 3.9 非決定性有限オートマトン（Nondeterministic Finite Automaton, NFA）は5つ組 \(M = (Q, \Sigma, \delta, q_0, F)\) である。ここで、次のとおりとする。

• \(Q\), \(\Sigma\), \(q_0\), \(F\) は DFA と同じ
• \(\delta: Q \times \Sigma \to \mathcal{P}(Q)\)：遷移関数（\(\mathcal{P}(Q)\) は Q の冪集合）

本節では ε を許さない NFA を扱う（ε を含む拡張は次節の ε-NFA として分けて導入し、最終的に通常の NFA に変換する）。

定義 3.10 NFA M の拡張遷移関数 \(\hat{\delta}: Q \times \Sigma^{\ast} \to \mathcal{P}(Q)\) を次のように定義する。

• \(\hat{\delta}(q, \epsilon) = \{q\}\)
• \(\hat{\delta}(q, wa) = \bigcup_{r \in \hat{\delta}(q, w)} \delta(r, a)\)

状態集合への拡張：\(\hat{\delta}(R, w) = \bigcup_{q \in R} \hat{\delta}(q, w)\)（\(R \subseteq Q\)）

定義 3.11 NFA \(M\) が \(w\) を受理 \(\Leftrightarrow\) \(\hat{\delta}(q_0, w) \cap F \ne \emptyset\)

例 3.3 末尾から3番目の文字が1である2進文字列を認識する NFA

直観的に、「今読んでいる文字が末尾から3番目の1である」と「推測」する。

\(M = (\{q_0, q_1, q_2, q_3\}, \{0, 1\}, \delta, q_0, \{q_3\})\)。ここで：

• \(\delta(q_0, 0) = \{q_0\}, \delta(q_0, 1) = \{q_0, q_1\}\)
• \(\delta(q_1, 0) = \{q_2\}, \delta(q_1, 1) = \{q_2\}\)
• \(\delta(q_2, 0) = \{q_3\}, \delta(q_2, 1) = \{q_3\}\)
• \(\delta(q_3, 0) = \emptyset, \delta(q_3, 1) = \emptyset\)

3.2.3 ε-NFA

定義 3.12 ε-NFA は、空文字列 ε での遷移を許す NFA である。

遷移関数：\(\delta: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q)\)

定義 3.13 状態 q のε-閉包 \(ECLOSE(q)\)：

\(ECLOSE(q) = \{p \mid \text{q から p へ ε 遷移のみで到達可能}\}\)

集合への拡張：\(ECLOSE(R) = \bigcup_{q \in R} ECLOSE(q)\)

例 3.4 ε-NFA から通常の NFA への変換

ε-NFA の遷移関数 \(\delta\) から、等価な NFA の遷移関数 \(\delta^{\prime}\) を構成： \(\delta^{\prime}(q, a) = ECLOSE(\bigcup_{r \in ECLOSE(q)} \delta(r, a))\)

3.2.4 DFAとNFAの等価性

定理 3.1 すべての NFA に対して、同じ言語を認識する DFA が存在する。

証明（部分集合構成法）： NFA \(N = (Q_N, \Sigma, \delta_N, q_0, F_N)\) から DFA \(D = (Q_D, \Sigma, \delta_D, q_{0,D}, F_D)\) を構成：

• \(Q_D = \mathcal{P}(Q_N)\)（N の状態集合の冪集合）
• \(q_{0,D} = \{q_0\}\)
• \(F_D = \{\,R \subseteq Q_N \mid R \cap F_N \ne \emptyset\,\}\)
• \(\delta_D(R, a) = \bigcup_{q \in R} \delta_N(q, a)\)

帰納法により、\(\hat\delta_D(\{q_0\}, w) = \hat\delta_N(q_0, w)\) が示される。 したがって、\(L(D) = L(N)\)。□

注意：状態数は最悪の場合指数的に増加する（\(\lvert Q_D\rvert \le 2^{\lvert Q_N\rvert}\)）。

3.3 正規言語

3.3.1 正規表現

定義 3.14 アルファベット Σ 上の正規表現（regular expression）を帰納的に定義：

1. ∅ は正規表現（言語 ∅ を表す）
2. ε は正規表現（言語 {ε} を表す）
3. a ∈ Σ に対して、a は正規表現（言語 {a} を表す）
4. \(R_1\), \(R_2\) が正規表現なら、以下も正規表現：
   • (R_1 + R_2)：和集合 L(R_1) ∪ L(R_2) を表す
   • (R_1R_2)：連結 L(R_1)L(R_2) を表す
   • (R_1)*：クリーネ閉包 \(L(R_1)^{\ast}\) を表す

記法の簡略化：

• 括弧の省略：優先順位は * > 連結 > +
• R+ = RR*
• R? = R + ε（0回または1回）

例 3.5 正規表現と言語：

• (0+1)*：すべての2進文字列
• 0*10*：ちょうど1つの1を含む2進文字列
• (0+1)*11(0+1)*：部分文字列として11を含む
• ((0+1)(0+1))*：偶数長の2進文字列

3.3.2 正規表現からNFAへの変換プロセス

なぜこの変換が重要なのか？

正規表現は人間にとって直感的で記述しやすい形式ですが、実際にコンピュータで文字列照合を行うには、オートマトンという実実行可能な機械に変換する必要があります。この変換プロセスを理解することで、以下が可能になります：

1. 正規表現エンジンの仕組み：grep、sedなどのツールの内部動作
2. コンパイラの字句解析器：トークン認識の自動化
3. 理論と実践の橋渡し：抽象的な言語記述から具体的な実装まで

Thompson構成法による段階的変換

正規表現 R に対するNFA N(R) を以下の帰納的構成で作成します：

直観図：Thompson 構成の各規則（リテラル・連結・和・クリーネ閉包）

実装の注意：ε-遷移を含むため、遷移計算では ε-閉包（ε で到達可能な状態の集合）を前計算・都度適用すると効率的。

Step 1: 基本ケース

1. 空集合 ∅:

   ○ (開始・非受理状態のみ)
   

2. 空文字列 ε:

   ○ → ◎
   開始  受理
   

3. 単一文字 a:

   ○ --a--> ◎
   開始      受理
   

Step 2: 帰納ケース

2.1 和集合 (R_1 + R_2)

      ε    N(R_1)    ε
○ ------> ○...○ -----> ◎
│                        ↑
│    ε    N(R_2)    ε     │
└------> ○...○ ----------┘
新開始              新受理

構成の詳細：

• 新しい開始状態から、\(R_1\) と \(R_2\) の NFA の開始状態へ ε 遷移
• \(R_1\) と \(R_2\) の NFA の受理状態から新しい受理状態へ ε 遷移
• 元の受理状態は非受理状態に変更

2.2 連結 (R_1R_2)

N(R_1)      ε      N(R_2)
○...○ ----------> ○...◎
開始  旧受理     新開始  受理

構成の詳細：

• \(R_1\) の NFA の受理状態から、\(R_2\) の NFA の開始状態へ ε 遷移
• \(R_1\) の旧受理状態は非受理に変更
• \(R_2\) の受理状態がそのまま全体の受理状態

2.3 クリーネ閉包 (R_1*)

	    ε (0回繰り返し用)
○ -----------------> ◎
│   ε      N(R_1)     ↑
└-----> ○...○ -------┘
新開始      │    ε   新受理
	           │ ε
	           └---------┘
	           (繰り返し用)

構成の詳細：

• 新しい開始状態から新しい受理状態へε遷移（0回繰り返し）
• 新しい開始状態から \(R_1\) の開始状態へ ε 遷移
• \(R_1\) の受理状態から新しい受理状態へ ε 遷移
• \(R_1\) の受理状態から \(R_1\) の開始状態へ ε 遷移（繰り返し）

具体例：(0+1)*0 の変換過程

Step 1: 基本要素の構築

"0": ○1 --0--> ○2
"1": ○3 --1--> ○4  

Step 2: (0+1) の構築

      ε
○0 -----> ○1 --0--> ○2 --ε--> ○5
│                              ↑
│    ε                  ε      │
└-----> ○3 --1--> ○4 --------┘

Step 3: (0+1)* の構築

    ε
○6 -----> ○7
│    ε      ↑
└-----> [0+1のNFA] --ε--> ○7
       │                   ↑
       │ ε                 │
       └-------------------┘

Step 4: 最終的に “0” を連結

[(0+1)*のNFA] --ε--> ○8 --0--> ○9
                              受理

変換アルゴリズムの性質：

1. 効率性：
   • 正規表現の長さを n とすると、O(n) の状態数
   • 線形時間での構成が可能
2. ε遷移の役割：
   • 構造的な接続を単純化
   • 後でε除去により通常のNFAに変換可能
3. 一意性：
   • 一つの開始状態、一つの受理状態
   • 構造的に明確な変換規則

実装上の考慮事項：

# Pythonによる変換アルゴリズムの実装例
def regex_to_nfa(regex):
    if regex == "∅":
        return create_empty_nfa()
    elif regex == "ε":
        return create_epsilon_nfa()
    elif is_single_char(regex):
        return create_char_nfa(regex)
    elif is_union(regex):
        r1, r2 = split_union(regex)
        return union_nfa(regex_to_nfa(r1), regex_to_nfa(r2))
    elif is_concat(regex):
        r1, r2 = split_concat(regex)
        return concat_nfa(regex_to_nfa(r1), regex_to_nfa(r2))
    elif is_star(regex):
        r = extract_star_operand(regex)
        return star_nfa(regex_to_nfa(r))

よくある落とし穴（実装と学習の注意）：

1. 演算子の優先順位と結合規則
   • 一般に * > 連結 > +（和）の優先順位で扱う
   • 暗黙の連結（例：ab）をトークナイズ段階で明示する記号に変換すると実装が安定
2. 括弧の整合性
   • 構文解析前に括弧の対応を検査。エラーメッセージを明確に
3. ε遷移の爆発
   • 構成直後のNFAはε遷移が多い。DFA化前にε-閉包を正しく実装（ECLOSE）
   • 可能なら不要なεを簡約する（ただし正当性を保つ）
4. 受理状態の取り扱い
   • Thompson構成では各サブNFAに「単一の開始・受理」を保つことがバグ回避に有効
5. 正規表現拡張への対応範囲
   • 文字クラス、任意文字 ., 繰り返し {m,n} 等は本章の最小核からは外れる。拡張する場合は個別に構成規則を追加

検証用ミニテスト（想定受理集合の要点）：

• 0*10*：ちょうど1個の 1 を含む（二重の 1 は拒否）
• (01+10)*：01 または 10 の繰り返しのみで構成
• ((0+1)(0+1))*：偶数長のみ受理
• (0+1)*11(0+1)*：部分文字列として 11 を含む

3.3.3 正規言語の特徴付け

定理 3.2（Kleeneの定理）言語 L について、以下は同値：

1. L は正規表現で表される
2. L は DFA で認識される
3. L は NFA で認識される

証明の概要： （1）から（3）：正規表現から NFA を帰納的に構成

• 基底：∅, ε, a に対する NFA は自明
• 帰納：和集合、連結、クリーネ閉包に対する構成法

（3）から（2）：定理3.1（部分集合構成法）

（2）から（1）：状態消去法または Arden の補題を使用□

3.3.4 正規言語の閉包性

定理 3.3 正規言語は以下の演算に関して閉じている：

1. 和集合
2. 共通部分（intersection）
3. 補集合
4. 連結
5. クリーネ閉包
6. 差集合
7. 対称差

証明（共通部分の場合）： \(L_1\) を認識する DFA \(M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)\) \(L_2\) を認識する DFA \(M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)\)

積オートマトン \(M = (Q_1 \times Q_2, \Sigma, \delta, (q_1, q_2), F_1 \times F_2)\) を構成： \(\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a))\)

帰納法により、\(\hat{\delta}((q_1, q_2), w) = (\hat{\delta}_1(q_1, w), \hat{\delta}_2(q_2, w))\) が示される。 したがって、\(L(M) = L_1 \cap L_2\)。□

3.3.5 正規言語の判定問題

定理 3.4 正規言語に対する以下の問題は決定可能：

1. 所属問題：w ∈ L?
2. 空問題：L = ∅?
3. 有限性問題：L は有限？
4. 等価性問題：\(L_1 = L_2\)?

証明（等価性問題）： \(L_1 = L_2 ⟺ (L_1 \setminus L_2) \cup (L_2 \setminus L_1) = \emptyset\) 正規言語の閉包性より \((L_1 \setminus L_2) \cup (L_2 \setminus L_1)\) も正規言語。 空問題が決定可能なので、等価性も決定可能。□

3.4 正規言語の限界

3.4.1 ポンピング補題（Pumping Lemma）の動機と直観

なぜポンピング補題（Pumping Lemma）が必要なのか？

正規言語には本質的な限界があります。例えば、「同数の0と1が並んだ文字列」\(\{0^{n}1^{n} \mid n \ge 0\}\) のような言語は、直感的に「数を数える必要がある」ため、有限の記憶しか持たない有限オートマトンでは認識できないと感じられます。しかし、この直感を厳密に証明するにはどうすればよいでしょうか？

ポンピング補題（Pumping Lemma）の基本的なアイデア

ポンピング補題（Pumping Lemma）は「鳩の巣原理」に基づいています：

1. 有限オートマトンの制約：
   • 有限オートマトンは有限個の状態しか持たない
   • 十分長い文字列を処理すると、必ず同じ状態を2回以上通る
2. ループの存在：
   • 同じ状態を2回通るということは「ループ」が存在する
   • このループ部分は何度でも繰り返すことができる
3. 「ポンピング」現象：
   • ループを0回、1回、2回、…と繰り返しても、言語に含まれたままでなければならない
   • これが「ポンピング」（pumping = 膨らませる）の名前の由来

視覚的理解：

状態遷移図での長い文字列の処理：
q_0 --x--> q_j --y--> q_j --z--> q_f
          ↑      ↓
          +------+
          (ループ)

- x: ループに入るまでの部分
- y: ループ部分（何度でも繰り返し可能）
- z: ループを出てから最終状態までの部分

直感的な例： 言語 L = \(\{0^{n}1^{n} \mid n \ge 0\}\) を考えてみましょう。もしこれが有限オートマトンで認識できるなら、十分長い文字列 000…111 を処理するとき、最初の0の部分でループが生じるはずです。しかし、そのループを余分に回ると、0の個数が増えて1の個数と合わなくなってしまいます。これが矛盾の源です。

ポンピング補題（Pumping Lemma）の役割：

• 証明ツール：「正規言語でないこと」を証明する標準的な手法
• 限界の発見：有限オートマトンでは表現できない言語パターンの特定
• 理論的基盤：計算モデルの表現力の限界を明確化

3.4.2 ポンピング補題（Pumping Lemma）の形式化

定理 3.5（正規言語のポンピング補題, Pumping Lemma）

L が正規言語ならば、ある正整数 p（pumping length）が存在して、 \(\lvert s\rvert \ge p\) なる任意の \(s \in L\) は以下を満たす分解 \(s = xyz\) を持つ：

1. \(\lvert xy\rvert \le p\)（ループは文字列の前半部分にある）
2. \(\lvert y\rvert > 0\)（ループ部分は空でない）
3. すべての \(i \ge 0\) に対して \(xy^{i}z \in L\)（ループを何度繰り返しても言語に含まれる）

各条件の意味：

1. 条件1（\(\lvert xy\rvert \le p\)）：ループは文字列の最初の p 文字以内で発生する
2. 条件2（\(\lvert y\rvert > 0\)）：ループ部分は実際に存在する（自明でない）
3. 条件3（すべての \(i \ge 0\) で \(xy^{i}z \in L\)）：ループを0回、1回、2回、…繰り返しても言語に含まれる

補題の使い方：

• 直接的使用：正規言語であることを確認する場合（稀）
• 対偶での使用：正規言語でないことを証明する場合（一般的）

対偶：「任意の \(p > 0\) に対して、\(\lvert s\rvert \ge p\) なる \(s \in L\) が存在し、s のどんな分解 \(s = xyz\) でも3つの条件のうち少なくとも1つが破られる ⟹ L は正規言語でない」

証明：L を認識する DFA を \(M = (Q, \Sigma, \delta, q_0, F)\) とし、\(p = \lvert Q\rvert\) とする。 \(\lvert s\rvert \ge p\) なる \(s \in L\) を考える。\(s = a_1a_2\cdots a_n\)（\(n \ge p\)）とする。

状態列 \(r_0, r_1, \ldots, r_n\) を以下のように定義：

• \(r_0 = q_0\)
• \(r_{i+1} = \delta(r_i, a_{i+1})\)

鳩の巣原理より、\(r_0, r_1, \ldots, r_p\) の中に同じ状態が存在。 \(r_j = r_k\)（\(0 \le j < k \le p\)）とすると、s = xyz と分解できる：

• \(x = a_1\cdots a_j\)
• \(y = a_{j+1}\cdots a_k\)
• \(z = a_{k+1}\cdots a_n\)

このとき：

1. \(\lvert xy\rvert = k \le p\)
2. \(\lvert y\rvert = k - j > 0\)
3. \(\hat\delta(q_0, x) = r_j = r_k = \hat\delta(q_0, xy)\) なので、y の部分はループを形成し、任意の \(i \ge 0\) に対して \(\hat\delta(q_0, xy^i z) \in F\) となる。したがって \(xy^i z \in L\)。□

3.4.3 非正規言語の例

例 3.6 L = \(\{0^{n}1^{n} \mid n \ge 0\}\) は正規言語でない。

証明（ポンピング補題の対偶を使用）： L が正規言語と仮定し、pumping length を p とする。 s = \(0^p1^p\) を考える。\(\lvert s\rvert = 2p \ge p\) なので、s = xyz と分解できる。

条件 \(\lvert xy\rvert \le p\) より、y は 0 のみからなる。y = \(0^k\)（k > 0）とする。 すると \(xy^2z = 0^{p+k}1^p\) となり、\(xy^2z \notin L\) で矛盾。□

例 3.7 以下の言語も非正規：

1. \(\{ww \mid w \in \{0,1\}^{\ast}\}\)
2. \(\{0^{n^2} \mid n \ge 0\}\)
3. \(\{w \in \{0,1\}^{\ast} \mid w \text{ は回文}\}\)

3.4.4 Myhill–Nerodeの定理

定義 3.15 言語 L に対して、文字列 x, y の識別可能性：

\(x \equiv_L y \iff \forall z \in \Sigma^{\ast},\ (xz \in L \iff yz \in L)\)

\(\equiv_L\) は同値関係であり、その同値類を L の右同値類という。

定理 3.6（Myhill–Nerodeの定理）

言語 L が正規言語 ⟺ \(\equiv_L\) の同値類の個数が有限

証明（\(\Rightarrow\)）：L を認識する DFA \(M = (Q, \Sigma, \delta, q_0, F)\) が存在。 \(x \equiv_M y\) ⟺ \(\hat{\delta}(q_0, x) = \hat{\delta}(q_0, y)\) と定義すると、\(\equiv_M\) は有限個の同値類を持つ。 \(x \equiv_M y\) ならば \(x \equiv_L y\) が示せるので、\(\equiv_L\) も有限個の同値類を持つ。

（\(\Leftarrow\)）：\(\equiv_L\) の同値類を状態とする DFA を構成できる。□

最小DFAとの関係（実務的な見方）

• 右同値関係 \(\equiv_L\) の同値類の個数 = L を受理する DFA の状態数の下界。
• ひいては、最小DFAの状態数 = \(\equiv_L\) の同値類の個数。
• 実際の最小化（状態分割法）は、\(\equiv_L\) を近似的に精緻化していく過程として理解できる。

（直観図）入力を区別できる拡張（後続文字列 z）をぶら下げたときに、異なる受理/拒否を生む先頭の接頭辞が異なる“ふるまい（右コンテキスト）”を定める。これが同値類の区別になり、その数が最小DFAの状態数に一致する。

3.5 文脈自由言語

3.5.1 文脈自由文法

定義 3.16 文脈自由文法（Context-Free Grammar, CFG）は4つ組 \(G = (V, \Sigma, R, S)\) である：

• V：変数（非終端記号）の有限集合
• Σ：終端記号の有限集合（V ∩ Σ = ∅）
• R：生成規則の有限集合。各規則は \(A \to \alpha\) の形（\(A \in V\), \(\alpha \in (V \cup \Sigma)^{\ast}\)）
• S ∈ V：開始記号

定義 3.17 導出（derivation）：

• 直接導出：\(A \to \alpha \in R\) のとき \(uAv \Rightarrow u\alpha v\)
• 導出：\(\Rightarrow^{\ast}\) は \(\Rightarrow\) の反射推移閉包
• 左導出：常に最左の変数を展開
• 右導出：常に最右の変数を展開

定義 3.18 CFG G が生成する言語：

\(L(G) = \{w \in \Sigma^{\ast} \mid S \Rightarrow^{\ast} w\}\)

例 3.8 言語 \(\{0^{n}1^{n} \mid n \ge 0\}\) を生成する CFG：

\(G = (\{S\}, \{0, 1\}, \{S \to 0S1, S \to \varepsilon\}, S)\)

導出例：\(S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 000111\)

3.5.2 導出木と曖昧性

定義 3.19 CFG G の導出木（derivation tree）は以下を満たす順序木：

1. 各内部節点は変数でラベル付け
2. 各葉は終端記号または ε でラベル付け
3. 根は開始記号でラベル付け
4. 内部節点 A の子が \(B_1, \ldots, B_k\) なら \(A \to B_1\cdots B_k \in R\)

定義 3.20 CFG \(G\) が曖昧（ambiguous）\(\Leftrightarrow\)

ある w ∈ L(G) に対して複数の導出木が存在

例 3.9 曖昧な文法：

\(G: E \to E + E \mid E \times E \mid (E) \mid a\)

文字列 “a + a × a” に対する2つの導出木：

1. \(E \to E + E \to a + E \to a + E \times E \to a + a \times a\)
2. \(E \to E \times E \to E + E \times E \to a + E \times E \to a + a \times E \to a + a \times a\)

3.5.3 文脈自由言語の標準形

定義 3.21 Chomsky標準形（CNF）：すべての生成規則が以下の形：

• \(A \to BC\)（\(A, B, C \in V\)）
• \(A \to a\)（\(A \in V, a \in \Sigma\)）
• \(S \to \varepsilon\)（S が右辺に現れない場合のみ）

定理 3.7 すべての CFG は等価な CNF に変換できる。

変換アルゴリズム：

1. ε-規則の除去（\(S \to \varepsilon\) 以外）
2. 単位規則（\(A \to B\)）の除去
3. 無用な記号の除去
4. 長い規則の分解
5. 終端記号の分離

定義 3.22 Greibach標準形（GNF）：すべての生成規則が以下の形：

\(A \to a\alpha\)（\(A \in V\), \(a \in \Sigma\), \(\alpha \in V^{\ast}\)）

3.5.4 CFGのポンピング補題（Pumping Lemma）

定理 3.8（文脈自由言語のポンピング補題, Pumping Lemma）

L が文脈自由言語ならば、ある正整数 p が存在して、 \(\lvert s\rvert \ge p\) なる任意の \(s \in L\) は以下を満たす分解 \(s = uvxyz\) を持つ：

1. \(\lvert vxy\rvert \le p\)
2. \(\lvert vy\rvert > 0\)
3. すべての \(i \ge 0\) に対して \(uv^{i}xy^{i}z \in L\)

証明の概要：CNF の文法を考え、十分長い文字列の導出木は深くなる。 鳩の巣原理により、ある変数が経路上に2回現れる。 その部分木の構造から、pumping が可能であることが示される。□

例 3.10 L = \(\{a^{n}b^{n}c^{n} \mid n \ge 0\}\) は文脈自由言語でない。

証明：pumping length を p とし、\(s = a^pb^pc^p\) を考える。 s = uvxyz と分解したとき、\(\lvert vxy\rvert \le p\) より、vxy は高々2種類の文字を含む。 したがって、\(uv^2xy^2z\) では3種類の文字の個数が等しくならない。□

3.6 プッシュダウンオートマトン

直観図：括弧整合を受理する PDA のスタック操作例

3.6.1 PDAの定義

定義 3.23 プッシュダウンオートマトン（PDA）は7つ組 \(P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)\)：

• Q：状態の有限集合
• Σ：入力アルファベット
• Γ：スタックアルファベット
• \(\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^{\ast})\)：遷移関数（\(\mathcal{P}\) は冪集合、有限部分集合のみを返す）
• \(q_0 \in Q\)：初期状態
• \(Z_0 \in \Gamma\)：初期スタック記号
• F ⊆ Q：受理状態の集合

定義 3.24 PDA の瞬時記述（ID）：\((q, w, \alpha) \in Q \times \Sigma^{\ast} \times \Gamma^{\ast}\)

• q：現在の状態
• w：未読の入力
• α：スタックの内容（左端がトップ）

定義 3.25 1ステップ遷移 \(\vdash\)：

\((q, aw, Z\alpha) \vdash (p, w, \beta\alpha)\) は \((p, \beta) \in \delta(q, a, Z)\) のときに成り立つ。

3.6.2 PDAの受理方式

定義 3.26 PDAの2つの受理方式：

1. 最終状態による受理：\(L(P) = \{w \mid (q_0, w, Z_0) \vdash^{\ast} (q, \epsilon, \alpha),\ q \in F\}\)
2. 空スタックによる受理：\(N(P) = \{w \mid (q_0, w, Z_0) \vdash^{\ast} (q, \epsilon, \epsilon)\}\)

直観図：最終状態受理 vs 空スタック受理

定理 3.9 最終状態受理と空スタック受理は等価である。

3.6.3 CFGとPDAの等価性

定理 3.10 言語 L について、以下は同値：

1. L は文脈自由言語
2. L は PDA で受理される

証明の概要： （1）から（2）：CFG から PDA を構成。スタックを使って左導出をシミュレート。

（2）から（1）：PDA から CFG を構成。変数 [q, A, p] は「状態 q でスタックトップ A から始めて、スタックトップを取り除いて状態 p に至る」ことを表す。□

3.7 文脈自由言語の性質

3.7.1 閉包性

定理 3.11 文脈自由言語は以下に関して閉じている：

1. 和集合
2. 連結
3. クリーネ閉包
4. 正規言語との共通部分

文脈自由言語は共通部分、補集合に関して閉じていない。

例 3.11 \(L_1 = \{a^{n}b^{n}c^{m} \mid n, m \ge 0\}\) と \(L_2 = \{a^{m}b^{n}c^{n} \mid n, m \ge 0\}\) は文脈自由言語だが、\(L_1 \cap L_2 = \{a^{n}b^{n}c^{n} \mid n \ge 0\}\) は文脈自由言語でない。

3.7.2 決定問題

定理 3.12 文脈自由言語に対する以下の問題は決定可能：

1. 所属問題：w ∈ L?（CYKアルゴリズム：\(O(n^3\lvert G\rvert)\)）
2. 空問題：L = ∅?
3. 有限性問題：L は有限？

以下は決定不能：

• 等価性問題：\(L_1 = L_2\)?
• 包含問題：\(L_1 \subseteq L_2\)?
• 曖昧性問題：CFG は曖昧？

3.7.3 決定性文脈自由言語

定義 3.27 決定性PDA（DPDA）：各構成で高々1つの遷移が可能

定義 3.28 決定性文脈自由言語（DCFL）：DPDA で受理される言語

性質：

• すべての正規言語は DCFL
• DCFL ⊂ CFL（真部分集合）
• DCFL は補集合に関して閉じている

まとめ

• 正規言語は DFA/NFA/正規表現で等価に記述でき、最小化により同値な DFA を一意に（同型まで）得られる
• 文脈自由言語は CFG と PDA が等価で、正規言語より表現力が強いが閉包性に制限がある
• 非正規性・非CFL性はポンピング補題や Myhill–Nerode（正規言語）で示すのが基本戦略
• 実用面では字句解析（正規言語）と構文解析（CFL）が現実のツールチェーンを支えている

次章への橋渡し

第3章で見たのは、計算モデルごとの表現力の差でした。次章ではその視点をさらに押し進め、そもそもどのモデルでも解けない問題が存在することを、対角化と還元によって示します。

補助資料を併用するなら、手を動かす確認は 付録B の第3章節、現実の接続は 付録E の第3章節、理解確認は 付録F の第3章節を参照してください。

参考文献と次の一歩

• 図版の再参照: 本章の図をまとめて見返したいときは 付録H: 図版ガイドと図一覧 を参照してください。
• 標準: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, 『Introduction to Automata Theory, Languages, and Computation』. DFA/NFA/CFG/PDA を体系的に学ぶための定番です。
• 補助: Dexter C. Kozen, 『Automata and Computability』. 証明の密度を保ちつつ、オートマトンから計算可能性までを短く見通したい読者に向いています。
• 出典メモ: 正規言語の特徴づけでは Myhill と Nerode の古典的結果が中核にあります。非正規性の証明戦略を固めたい場合は、本章の Myhill–Nerode とポンピング補題を比較しながら読むのが有効です。
• 次の一歩: 形式言語の表現力から計算不能性へ視野を広げるなら第4章へ進んでください。証明の手を動かしたい場合は 付録C（第3章の追加演習） が最短の復習導線です。

  章末問題

注: 章内の代表的な追加演習と詳細解答は 付録C を参照。

• 正規言語の証明: 付録C（ex-3-1）
• 文脈自由文法の設計: 付録C（ex-3-2）
• CFL でない言語の証明（ポンピング補題）: 付録C（ex-3-3）
• Myhill–Nerode による非正規性の証明（追加例）: 付録C（ex-3-5）

取り組み方ガイド

迷ったら次の表の順で進め、詰まったら「主に戻る節」にある定義・構成例・反例を先に見直してください。

基礎問題

1. 以下の言語を認識する DFA を構成せよ： (a) \(\{w \in \{0,1\}^{\ast} \mid w \text{ は部分文字列 } 00 \text{ を含まない}\}\) (b) \(\{w \in \{a,b\}^{\ast} \mid w \text{ 中の } a \text{ の個数は } 3 \text{ の倍数}\}\) (c) \(\{w \in \{0,1\}^{\ast} \mid w \text{ を2進数と見たとき } 3 \text{ で割り切れる}\}\)

   ヒント:

   • (a) 直前の文字を1ビット記憶する2状態＋罠状態の設計。
   • (b) a の個数を mod 3 で管理する3状態DFA。
   • (c) これも mod 3 の剰余遷移（ビット左シフト+加算に対応）。

2. 以下の言語を表す正規表現を示せ： (a) \(\{w \in \{a,b\}^{\ast} \mid w \text{ は } aa \text{ も } bb \text{ も含まない}\}\) (b) \(\{w \in \{0,1\}^{\ast} \mid w \text{ のすべての } 0 \text{ のブロックの長さは偶数}\}\)

   ヒント: (b) 0 の塊は (00)+ として表れ、1 によって区切られることを利用。

3. 以下の言語が正規言語でないことを証明せよ： (a) \(\{0^{n}1^{m} \mid n \ne m\}\) (b) \(\{w \in \{0,1\}^{\ast} \mid w \text{ は同数の } 0 \text{ と } 1 \text{ を含む}\}\)

   ヒント: ポンピング補題で反証。あるいは Myhill–Nerode の無限同値類（カウント差で区別）。

4. 以下の言語を生成する CFG を構成せよ： (a) \(\{a^{i}b^{j}c^{k} \mid i = j \text{ または } j = k\}\) (b) \(\{w \in \{a,b\}^{\ast} \mid w = w^{R}\}\)（回文）

5. PDA を用いて、バランスの取れた括弧列を認識する方法を示せ。

発展問題

1. DFA の最小化アルゴリズムを説明し、その正当性を証明せよ。

   ヒント: 初期分割 {F, Q\F} から開始する分割精緻化（Hopcroft など）。

2. 正規表現から ε-NFA への変換アルゴリズムを詳述せよ。

3. Myhill–Nerode の定理を用いて、以下の言語の最小DFAの状態数の下界（ひいては最小状態数）を示せ： (a) \(L_1 = \{ w \in \{a,b\}^{\ast} \mid w \text{ が部分文字列 } aba \text{ を含む }\}\) 提示: 接頭辞 ε, a, ab, aba が互いに識別可能であることを示す（よって 4 状態が必要） (b) \(L_2 = \{ w \in \{0,1\}^{\ast} \mid w \text{ 中の } 1 \text{ の個数は } 3 \text{ の倍数で、最終文字が } 0 \}\) 提示: 3（1 の剰余）×2（最終文字）= 6 通りの右コンテキストを区別する必要がある

   (c) \(L_3 = \{ w \in \{0,1\}^{\ast} \mid w \text{ を二進数として解釈した値が } 5 \text{ の倍数 }\}\) 提示: 5 つの剰余類（mod 5）の右コンテキストが必要なので、下界は 5 (d) \(L_4 = \{ w \in \{0,1\}^{\ast} \mid w \text{ を二進数として解釈した値が } 7 \text{ の倍数 }\}\) 提示: 7 つの剰余類（mod 7）で区別可能なので、下界は 7

4. \(L_1\) が正規言語、\(L_2\) が文脈自由言語のとき、\(L_1 \cap L_2\) が文脈自由言語であることを証明せよ。

5. CYK アルゴリズムを説明し、その時間計算量を解析せよ。

ヒント: 三重ループで O(n^3 \(\lvert G\rvert\))。CNF への変換も前処理に含めて議論。

1. Myhill–Nerode の定理を用いて、以下の言語が正規言語でないことを示せ： \(L = \{0^{n}1^{n} \mid n \ge 0\}\)

ヒント: 接頭辞 \(0^0\), \(0^1\), \(0^2\), … が互いに識別可能であること（右コンテキストが違うこと）を示す。

1. 以下の言語が文脈自由言語か決定せよ： (a) \(\{a^{n}b^{n}c^{n}d^{n} \mid n \ge 0\}\) (b) \(\{ww \mid w \in \{0,1\}^{\ast}\}\) (c) \(\{a^{i}b^{j}c^{k} \mid i < j < k\}\)

探究課題

1. オートマトン理論の実用的応用（コンパイラ、正規表現エンジン、XMLパーサなど）について調査し、理論と実装のギャップについて論ぜよ。

2. 文脈自由言語を超える言語クラス（文脈依存言語、帰納的可算言語など）について調査し、Chomskyの階層との関係を説明せよ。

実装課題

1. DFAとNFAのシミュレータを実装せよ

class DFA:
    def __init__(self, states, alphabet, transitions, start, accept_states):
        # DFAの初期化
    
    def accepts(self, string):
        # 文字列を受理するか判定
        
class NFA:
    def __init__(self, states, alphabet, transitions, start, accept_states):
        # NFAの初期化（ε遷移も含む）
    
    def to_dfa(self):
        # 部分集合構成法によりDFAに変換

2. 文脈自由文法のCYK構文解析アルゴリズムを実装せよ

• CNF（Chomsky標準形）の文法を入力として受け取る
• 動的計画法により、与えられた文字列が導出可能か判定
• 可能な場合は導出木も構成する