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

はじめに

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

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

3.1 形式言語

形式言語の基本概念

3.1.1 基本定義

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

例：

Σ₁ = {0, 1}（2進アルファベット）
Σ₂ = {a, b, c, …, z}（英小文字）
Σ₃ = {0, 1, …, 9, +, -, ×, ÷, (, )}（算術式の記号）

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

記法：

w ：文字列 w の長さ
wᵢ：w の i 番目の文字（1 ≤ i ≤ w ）
Σ*：Σ 上のすべての文字列の集合
Σ⁺：Σ 上の空でない文字列の集合（Σ⁺ = Σ* \ {ε}）
Σⁿ：長さ n の文字列の集合

定義 3.3 Σ 上の言語（language）は、Σ* の部分集合である。

3.1.2 文字列の演算

定義 3.4 文字列の基本演算：

連結（concatenation）：文字列 x, y の連結 xy は、x の後に y を続けた文字列
- 性質： xy = x + y
- 単位元：xε = εx = x
冪乗：wⁿ = ww…w（n 個の w の連結）
- w⁰ = ε
- wⁿ⁺¹ = wⁿw
逆転（reversal）：w = a₁a₂…aₙ の逆転 wᴿ = aₙ…a₂a₁
- εᴿ = ε
- (xy)ᴿ = yᴿxᴿ
部分文字列：v が w の部分文字列 ⟺ ∃x, y ∈ Σ*, w = xvy
- 接頭辞（prefix）：w = xv となる x
- 接尾辞（suffix）：w = vx となる x

3.1.3 言語の演算

定義 3.5 言語 L₁, L₂ ⊆ Σ* に対する演算：

和集合：L₁ ∪ L₂ = {w w ∈ L₁ ∨ w ∈ L₂}
積集合：L₁ ∩ L₂ = {w w ∈ L₁ ∧ w ∈ L₂}
補集合：L̄ = Σ* \ L
連結：L₁L₂ = {xy x ∈ L₁ ∧ y ∈ L₂}
冪乗：
- L⁰ = {ε}
- Lⁿ⁺¹ = LⁿL
クリーネ閉包：L* = ⋃ₙ₌₀^∞ Lⁿ
正閉包：L⁺ = ⋃ₙ₌₁^∞ Lⁿ

例 3.1 L = {0, 11} のとき：

L² = {00, 011, 110, 1111}
L* = {ε, 0, 11, 00, 011, 110, 1111, …}

3.1.4 形式言語の実用的応用

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

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

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

# 正規表現による形式検証
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, Σ, δ, q₀, F) である。ここで：

Q：状態の有限集合
Σ：入力アルファベット
δ: Q × Σ → Q：遷移関数
q₀ ∈ Q：初期状態
F ⊆ Q：受理状態の集合

定義 3.7 DFA M の拡張遷移関数 δ̂: Q × Σ* → Q を帰納的に定義：

δ̂(q, ε) = q
δ̂(q, wa) = δ(δ̂(q, w), a)（w ∈ Σ*, a ∈ Σ）

定義 3.8 DFA M が文字列 w を受理するとは、δ̂(q₀, w) ∈ F であること。 M が認識する言語：L(M) = {w ∈ Σ* | δ̂(q₀, w) ∈ F}

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

M = ({q₀, q₁}, {0, 1}, δ, q₀, {q₀}) where:

δ(q₀, 0) = q₁, δ(q₀, 1) = q₀
δ(q₁, 0) = q₀, δ(q₁, 1) = q₁

偶数個の0を認識するDFA

状態の意味：

q₀：これまでに読んだ0の個数が偶数（受理状態）
q₁：これまでに読んだ0の個数が奇数

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

定義 3.9 非決定性有限オートマトン（Nondeterministic Finite Automaton, NFA）は5つ組 M = (Q, Σ, δ, q₀, F) である。ここで：

Q, Σ, q₀, F は DFA と同じ
δ: Q × Σ → P(Q)：遷移関数（P(Q) は Q の冪集合）

定義 3.10 NFA M の拡張遷移関数 δ̂: Q × Σ* → P(Q)：

δ̂(q, ε) = {q}
δ̂(q, wa) = ⋃ᵣ∈δ̂(q,w) δ(r, a)

状態集合への拡張：δ̂(R, w) = ⋃q∈R δ̂(q, w)（R ⊆ Q）

定義 3.11 NFA M が w を受理 ⟺ δ̂(q₀, w) ∩ F ≠ ∅

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

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

M = ({q₀, q₁, q₂, q₃}, {0, 1}, δ, q₀, {q₃}) where:

δ(q₀, 0) = {q₀}, δ(q₀, 1) = {q₀, q₁}
δ(q₁, 0) = {q₂}, δ(q₁, 1) = {q₂}
δ(q₂, 0) = {q₃}, δ(q₂, 1) = {q₃}
δ(q₃, 0) = ∅, δ(q₃, 1) = ∅

3.2.3 ε-NFA

定義 3.12 ε-NFA は、空文字列 ε での遷移を許す NFA である。遷移関数：δ: Q × (Σ ∪ {ε}) → P(Q)

定義 3.13 状態 q のε-閉包 ECLOSE(q)： ECLOSE(q) = {p | q から p へ ε 遷移のみで到達可能}

集合への拡張：ECLOSE(R) = ⋃q∈R ECLOSE(q)

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

ε-NFA の遷移関数 δ から、等価な NFA の遷移関数 δ’ を構成： δ’(q, a) = ECLOSE(⋃ᵣ∈ECLOSE(q) δ(r, a))

3.2.4 DFAとNFAの等価性

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

証明（部分集合構成法）： NFA N = (Qₙ, Σ, δₙ, q₀, Fₙ) から DFA D = (Qᴅ, Σ, δᴅ, q₀ᴅ, Fᴅ) を構成：

Qᴅ = P(Qₙ)（N の状態集合の冪集合）
q₀ᴅ = {q₀}
Fᴅ = {R ⊆ Qₙ R ∩ Fₙ ≠ ∅}
δᴅ(R, a) = ⋃q∈R δₙ(q, a)

帰納法により、δ̂ᴅ({q₀}, w) = δ̂ₙ(q₀, w) が示される。したがって、L(D) = L(N)。□

注意：状態数は最悪の場合指数的に増加する（

Qᴅ

≤ 2^

Qₙ

）。

3.3 正規言語

正規言語と正規表現

3.3.1 正規表現

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

∅ は正規表現（言語 ∅ を表す）
ε は正規表現（言語 {ε} を表す）
a ∈ Σ に対して、a は正規表現（言語 {a} を表す）
R₁, R₂ が正規表現なら、以下も正規表現：
- (R₁ + R₂)：和集合 L(R₁) ∪ L(R₂) を表す
- (R₁R₂)：連結 L(R₁)L(R₂) を表す
- (R₁)：クリーネ閉包 L(R₁) を表す

記法の簡略化：

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

例 3.5 正規表現と言語：

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

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

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

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

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

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

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

Step 1: 基本ケース

空集合 ∅:
```
○ (開始・非受理状態のみ)
```
空文字列 ε:
```
○ → ◎
開始  受理
```
単一文字 a:
```
○ --a--> ◎
開始      受理
```

Step 2: 帰納ケース

2.1 和集合 (R₁ + R₂)

      ε    N(R₁)    ε
○ ------> ○...○ -----> ◎
│                        ↑
│    ε    N(R₂)    ε     │
└------> ○...○ ----------┘
新開始              新受理

構成の詳細：

新しい開始状態から、R₁とR₂のNFAの開始状態へε遷移
R₁とR₂のNFAの受理状態から新しい受理状態へε遷移
元の受理状態は非受理状態に変更

2.2 連結 (R₁R₂)

N(R₁)      ε      N(R₂)
○...○ ----------> ○...◎
開始  旧受理     新開始  受理

構成の詳細：

R₁のNFAの受理状態から、R₂のNFAの開始状態へε遷移
R₁の旧受理状態は非受理に変更
R₂の受理状態がそのまま全体の受理状態

2.3 クリーネ閉包 (R₁*)

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

構成の詳細：

新しい開始状態から新しい受理状態へε遷移（0回繰り返し）
新しい開始状態からR₁の開始状態へε遷移
R₁の受理状態から新しい受理状態へε遷移
R₁の受理状態からR₁の開始状態へε遷移（繰り返し）

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

Step 1: 基本要素の構築

"0": ○₁ --0--> ○₂
"1": ○₃ --1--> ○₄  

Step 2: (0+1) の構築

      ε
○₀ -----> ○₁ --0--> ○₂ --ε--> ○₅
│                              ↑
│    ε                  ε      │
└-----> ○₃ --1--> ○₄ --------┘

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

    ε
○₆ -----> ○₇
│    ε      ↑
└-----> [0+1のNFA] --ε--> ○₇
       │                   ↑
       │ ε                 │
       └-------------------┘

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

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

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

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

実装上の考慮事項：

# 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))

3.3.3 正規言語の特徴付け

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

L は正規表現で表される
L は DFA で認識される
L は NFA で認識される

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

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

(3)→(2)：定理3.1（部分集合構成法）

(2)→(1)：状態消去法またはArdenの補題を使用□

3.3.4 正規言語の閉包性

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

和集合
積集合
補集合
連結
クリーネ閉包
差集合
対称差

証明（積集合の場合）： L₁ を認識する DFA M₁ = (Q₁, Σ, δ₁, q₁, F₁) L₂ を認識する DFA M₂ = (Q₂, Σ, δ₂, q₂, F₂)

積オートマトン M = (Q₁ × Q₂, Σ, δ, (q₁, q₂), F₁ × F₂) を構成： δ((p, q), a) = (δ₁(p, a), δ₂(q, a))

帰納法により、δ̂((q₁, q₂), w) = (δ̂₁(q₁, w), δ̂₂(q₂, w)) が示される。したがって、L(M) = L₁ ∩ L₂。□

3.3.5 正規言語の判定問題

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

所属問題：w ∈ L?
空問題：L = ∅?
有限性問題：L は有限？
等価性問題：L₁ = L₂?

証明（等価性問題）： L₁ = L₂ ⟺ (L₁ \ L₂) ∪ (L₂ \ L₁) = ∅ 正規言語の閉包性より (L₁ \ L₂) ∪ (L₂ \ L₁) も正規言語。空問題が決定可能なので、等価性も決定可能。□

3.4 正規言語の限界

正規言語のPumping補題と限界

3.4.1 Pumping補題の動機と直観

なぜPumping補題が必要なのか？

正規言語には本質的な限界があります。例えば、「同数の0と1が並んだ文字列」{0ⁿ1ⁿ

n ≥ 0} のような言語は、直感的に「数を数える必要がある」ため、有限の記憶しか持たない有限オートマトンでは認識できないと感じられます。しかし、この直感を厳密に証明するにはどうすればよいでしょうか？

Pumping補題の基本的なアイデア

Pumping補題は「鳩の巣原理」に基づいています：

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

視覚的理解：

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

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

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

Pumping補題の役割：

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

3.4.2 Pumping補題の形式化

定理 3.5（正規言語のPumping補題） L が正規言語ならば、ある正整数 p（pumping length）が存在して、 |s| ≥ p なる任意の s ∈ L は以下を満たす分解 s = xyz を持つ：

xy ≤ p　（ループは文字列の前半部分にある）
y > 0　（ループ部分は空でない）
すべての i ≥ 0 に対して xyⁱz ∈ L　（ループを何度繰り返しても言語に含まれる）

各条件の意味：

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

補題の使い方：

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

対偶：「任意のp > 0に対して、

≥ pなるs ∈ Lが存在し、sのどんな分解s = xyzでも3つの条件のうち少なくとも1つが破られる ⟹ Lは正規言語でない」

証明：L を認識する DFA を M = (Q, Σ, δ, q₀, F) とし、p =	Q	とする。
	s	≥ p なる s ∈ L を考える。s = a₁a₂…aₙ（n ≥ p）とする。

状態列 r₀, r₁, …, rₙ を以下のように定義：

r₀ = q₀
rᵢ₊₁ = δ(rᵢ, aᵢ₊₁)

鳩の巣原理より、r₀, r₁, …, rₚ の中に同じ状態が存在。 rⱼ = rₖ（0 ≤ j < k ≤ p）とすると、s = xyz と分解できる：

x = a₁…aⱼ
y = aⱼ₊₁…aₖ
z = aₖ₊₁…aₙ

このとき：

xy = k ≤ p
y = k - j > 0
δ̂(q₀, x) = rⱼ = rₖ = δ̂(q₀, xy) なので、y の部分はループを形成し、任意の i ≥ 0 に対して δ̂(q₀, xyⁱz) ∈ F となる。したがって xyⁱz ∈ L。□

3.4.3 非正規言語の例

例 3.6 L = {0ⁿ1ⁿ

n ≥ 0} は正規言語でない。

証明（Pumping補題の対偶を使用）： L が正規言語と仮定し、pumping length を p とする。 s = 0ᵖ1ᵖ を考える。|s| = 2p ≥ p なので、s = xyz と分解できる。

条件 |xy| ≤ p より、y は 0 のみからなる。y = 0ᵏ（k > 0）とする。すると xy²z = 0ᵖ⁺ᵏ1ᵖ ∉ L となり、矛盾。□

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

{ww w ∈ {0,1}*}
{0ⁿ² n ≥ 0}
{w ∈ {0,1}* w は回文}

3.4.4 Myhill-Nerodの定理

定義 3.15 言語 L に対して、文字列 x, y の識別可能性： x ≡ₗ y ⟺ ∀z ∈ Σ*, (xz ∈ L ⟺ yz ∈ L)

≡ₗ は同値関係であり、その同値類を L の右同値類という。

定理 3.6（Myhill-Nerodの定理）言語 L が正規言語 ⟺ ≡ₗ の同値類の個数が有限

証明（⇒）：L を認識する DFA M = (Q, Σ, δ, q₀, F) が存在。 x ≡ₘ y ⟺ δ̂(q₀, x) = δ̂(q₀, y) と定義すると、≡ₘ は有限個の同値類を持つ。 x ≡ₘ y ならば x ≡ₗ y が示せるので、≡ₗ も有限個の同値類を持つ。

（⇐）：≡ₗ の同値類を状態とする DFA を構成できる。□

3.5 文脈自由言語

文脈自由言語と文法

3.5.1 文脈自由文法

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

V：変数（非終端記号）の有限集合
Σ：終端記号の有限集合（V ∩ Σ = ∅）
R：生成規則の有限集合。各規則は A → α の形（A ∈ V, α ∈ (V ∪ Σ)*）
S ∈ V：開始記号

定義 3.17 導出（derivation）：

直接導出：uAv ⇒ uαv if A → α ∈ R
導出：⇒* は ⇒ の反射推移閉包
左導出：常に最左の変数を展開
右導出：常に最右の変数を展開

定義 3.18 CFG G が生成する言語： L(G) = {w ∈ Σ* | S ⇒* w}

例 3.8 言語 {0ⁿ1ⁿ | n ≥ 0} を生成する CFG： G = ({S}, {0, 1}, {S → 0S1, S → ε}, S)

導出例：S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 000111

3.5.2 導出木と曖昧性

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

各内部節点は変数でラベル付け
各葉は終端記号または ε でラベル付け
根は開始記号でラベル付け
内部節点 A の子が B₁, …, Bₖ なら A → B₁…Bₖ ∈ R

定義 3.20 CFG G が曖昧（ambiguous）⟺ ある w ∈ L(G) に対して複数の導出木が存在

例 3.9 曖昧な文法： G: E → E + E | E × E | (E) | a

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

E → E + E → a + E → a + E × E → a + a × a
E → E × E → E + E × E → a + E × E → a + a × E → a + a × a

3.5.3 文脈自由言語の標準形

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

A → BC（A, B, C ∈ V）
A → a（A ∈ V, a ∈ Σ）
S → ε（S が右辺に現れない場合のみ）

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

変換アルゴリズム：

ε-規則の除去（S → ε 以外）
単位規則（A → B）の除去
無用な記号の除去
長い規則の分解
終端記号の分離

定義 3.22 Greibach標準形（GNF）：すべての生成規則が以下の形： A → aα（A ∈ V, a ∈ Σ, α ∈ V*）

3.5.4 CFGのPumping補題

定理 3.8（文脈自由言語のPumping補題） L が文脈自由言語ならば、ある正整数 p が存在して、 |s| ≥ p なる任意の s ∈ L は以下を満たす分解 s = uvxyz を持つ：

vxy ≤ p
vy > 0
すべての i ≥ 0 に対して uvⁱxyⁱz ∈ L

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

例 3.10 L = {aⁿbⁿcⁿ

n ≥ 0} は文脈自由言語でない。

証明：pumping length を p とし、s = aᵖbᵖcᵖ を考える。 s = uvxyz と分解したとき、|vxy| ≤ p より、vxy は高々2種類の文字を含む。したがって、uv²xy²z では3種類の文字の個数が等しくならない。□

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

プッシュダウンオートマトンの構造と機能

3.6.1 PDAの定義

定義 3.23 プッシュダウンオートマトン（PDA）は7つ組 P = (Q, Σ, Γ, δ, q₀, Z₀, F)：

Q：状態の有限集合
Σ：入力アルファベット
Γ：スタックアルファベット
δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)：遷移関数（Pは冪集合、有限部分集合のみを返す）
q₀ ∈ Q：初期状態
Z₀ ∈ Γ：初期スタック記号
F ⊆ Q：受理状態の集合

定義 3.24 PDA の瞬時記述（ID）：(q, w, α) ∈ Q × Σ* × Γ*

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

定義 3.25 1ステップ遷移 ⊢： (q, aw, Zα) ⊢ (p, w, βα) if (p, β) ∈ δ(q, a, Z)

3.6.2 PDAの受理方式

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

最終状態による受理：L(P) = {w (q₀, w, Z₀) ⊢* (q, ε, α), q ∈ F}
空スタックによる受理：N(P) = {w (q₀, w, Z₀) ⊢* (q, ε, ε)}

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

3.6.3 CFGとPDAの等価性

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

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

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

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

3.7 文脈自由言語の性質

文脈自由言語の性質と限界

3.7.1 閉包性

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

和集合
連結
クリーネ閉包
正規言語との積集合

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

例 3.11 L₁ = {aⁿbⁿcᵐ

n, m ≥ 0} と L₂ = {aᵐbⁿcⁿ

n, m ≥ 0} は文脈自由言語だが、L₁ ∩ L₂ = {aⁿbⁿcⁿ

n ≥ 0} は文脈自由言語でない。

3.7.2 決定問題

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

所属問題：w ∈ L?（CYKアルゴリズム：O(n³ G )）
空問題：L = ∅?
有限性問題：L は有限？

以下は決定不能：

等価性問題：L₁ = L₂?
包含問題：L₁ ⊆ L₂?
曖昧性問題：CFG は曖昧？

3.7.3 決定性文脈自由言語

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

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

性質：

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

章末問題

基礎問題

以下の言語を認識する DFA を構成せよ： (a) {w ∈ {0,1}* | w は 00 を部分文字列として含まない} (b) {w ∈ {a,b}* | w 中の a の個数は 3 の倍数} (c) {w ∈ {0,1}* | w を2進数と見たとき 3 で割り切れる}
以下の言語を表す正規表現を示せ： (a) {w ∈ {a,b}* | w は aa も bb も含まない} (b) {w ∈ {0,1}* | w のすべての 0 のブロックの長さは偶数}
以下の言語が正規言語でないことを証明せよ： (a) {0ⁿ1ᵐ | n ≠ m} (b) {w ∈ {0,1}* | w は同数の 0 と 1 を含む}
以下の言語を生成する CFG を構成せよ： (a) {aⁱbʲcᵏ | i = j または j = k} (b) {w ∈ {a,b}* | w = wᴿ}（回文）
PDA を用いて、バランスの取れた括弧列を認識する方法を示せ。

発展問題

DFA の最小化アルゴリズムを説明し、その正当性を証明せよ。
正規表現から ε-NFA への変換アルゴリズムを詳述せよ。
L₁ が正規言語、L₂ が文脈自由言語のとき、L₁ ∩ L₂ が文脈自由言語であることを証明せよ。
CYK アルゴリズムを説明し、その時間計算量を解析せよ。
以下の言語が文脈自由言語か決定せよ： (a) {aⁿbⁿcⁿdⁿ | n ≥ 0} (b) {ww | w ∈ {0,1}*} (c) {aⁱbʲcᵏ | i < j < k}

探究課題

オートマトン理論の実用的応用（コンパイラ、正規表現エンジン、XMLパーサなど）について調査し、理論と実装のギャップについて論ぜよ。
文脈自由言語を超える言語クラス（文脈依存言語、帰納的可算言語など）について調査し、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標準形）の文法を入力として受け取る
動的計画法により、与えられた文字列が導出可能か判定
可能な場合は導出木も構成する

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

はじめに

3.1 形式言語

3.1.1 基本定義

3.1.2 文字列の演算

3.1.3 言語の演算

3.1.4 形式言語の実用的応用

3.2 有限オートマトン

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

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

3.2.3 ε-NFA

3.2.4 DFAとNFAの等価性

3.3 正規言語

3.3.1 正規表現

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

3.3.3 正規言語の特徴付け

3.3.4 正規言語の閉包性

3.3.5 正規言語の判定問題

3.4 正規言語の限界

3.4.1 Pumping補題の動機と直観

3.4.2 Pumping補題の形式化

3.4.3 非正規言語の例

3.4.4 Myhill-Nerodの定理

3.5 文脈自由言語

3.5.1 文脈自由文法

3.5.2 導出木と曖昧性

3.5.3 文脈自由言語の標準形

3.5.4 CFGのPumping補題

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

3.6.1 PDAの定義

3.6.2 PDAの受理方式

3.6.3 CFGとPDAの等価性

3.7 文脈自由言語の性質

3.7.1 閉包性

3.7.2 決定問題

3.7.3 決定性文脈自由言語

章末問題

基礎問題

発展問題

探究課題

実装課題

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

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

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