計算理論の基礎
- 7.9 時間 (1 巻)
- 12.6 時間 (2 巻)
- 14.1 時間 (3 巻)
- 離散数学の基本中の基本は学んだ
- 計算理論については何も知らない状態
- 本のタイトル通り、オートマトンと言語を理解できた
- 有限オートマトン、プッシュダウン・オートマトン、正規言語、文脈自由言語
- 定義をしっかり与えて、証明していくやり方を思い出した
- この後の計算可能性と複雑さが楽しみ
- Turing Machine、判定可能性、帰着可能性について学んだ
- 計算可能性について理解した
- 帰着を利用した証明面白い
- P vs NP 問題、NP 完全性について理解した
- 時間の複雑さ、領域の複雑さ、階層定理について学んだ
- 他にも近似アルゴリズム、確率的アルゴリズム、交替性、対話証明系などについて学んだ
- 2 巻までの計算可能性についての議論に加え、問題の複雑さについて学べた
- 本書は、計算理論の重要な柱をなす 3 つの分野「オートマトン」「計算可能性」「複雑さ」についての教科書である
- これら 3 つの分野はすべて「計算機の本質的な能力とその限界は何か?」という疑問に関係している
- 複雑さの理論
- 何が、問題の難しさ・やさしさを決めているだろうか?
- 計算可能性の理論
- 複雑さの理論の目的は、問題をかんたんなものと難しいものに分類すること
- 計算可能性の理論の目的は、解を求められる問題とそうでない問題とに分類すること
- 数学的概念や用語
- 列
- 集合は対象とするものの集まりだったのに対し、ものをある順序で並べたものを列(sequence)という
- 組
- 有限な列は組(tuple)とも呼ばれる
- 定義域・値域
- 関数の入力になりうるものの集合を定義域(domain)という
- 関数の出力になり うるものの集合を値域(range)という
- f の定義域が D で値域が R である時、f: D → R のように表す
- 定義・定理・証明
- この 3 つは我々の計算の理論も含めて、すべての数学分野での中心となる
- 定義(definition)
- 我々が用いる「もの」や概念を規定する
- 証明(proof)
- 命題が真であることを納得させる論理的な議論のこと
- 定理(theorem)
- 真と証明された命題
- 系(corollary)
- 定理やその証明から、他の関連した命題も真であることが容易に示せる場合がある。そうした命題を、その定理の系という
- 証明を発見するための一般的な戦略
- 最初に、証明したい命題を注意深く読もう
- そして関連するすべての記法を理解しよう
- その上で、命題を読者自身の言葉で書き直してみよう
- さらに、命題をいくつかの部分に分けて、それぞれの部分を 1 つずつ考察するとよいだろう
- 証明を作成する時の秘訣
- 忍耐強さ / 繰り返し / きれいさ / 簡潔さ
- 「計算機とは何であるか?」計算の理論をこの問いから始める
- Markov 連鎖
- 有限オートマトンに確率的要素を許したもの
- 有限オートマトンの定義
- 有限オートマトンは 5 個組(Q, Σ, δ, q0, F)である
- Q は状態(state)と呼ばれる有限集合
- Σ はアルファベット(alphabet)と呼ばれる有限集合
- δ: Q × Σ → Q は状態関数(transition function)
- q0 ∈ Q は開始状態(start state)
- F ⊆ Q は受理状態の集合(set of accept states)
- 機械の言語
- A を機械 M が受理するすべての文字列の集合とするならば、A は機械 M の言語(language of machine M)であるといい、L(M) = A と書く
- また M は A を認識する、あるいは受理するという
- ある有限オートマトンで認識される言語を正規言語(regular language)という
- 正規演算
- A と B を言語とする。正規演算とは以下のように定義された和集合演算(union)、連結演算(concatenation)、スター演算(star)のいずれかである。A = {good, bad} かつ B = {boy, girl} とする
- 和集合演算: A ∪ B = {x | x ∈ A または x ∈ B}
- A ∪ B = {good, bad, boy, girl}
- 連結演算: A ❍ B = {xy | x ∈ A かつ y ∈ B}
- A ❍ B = {goodboy, goodgirl, badboy, badgirl}
- スター演算: A* = {x1x2...xk | k >= 0 であり、かつ各々の xi に対して xi ∈ A}
- A* = {ε, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, goodbadgood, goodbadbad, ... }
- 閉じている
- その集まりの要素への演算の結果が、またその集まりに含まれるものとなること
- 決定性
- 機会がある与えられた状態にあって、次の入力文字を読み出すと、次の状態が何である かが決まってる。このことを決定性(deterministic)計算と呼ぶ
- これに対して、非決定性(nondeterministic)機会の場合には、どの時点においても次の状態として複数の選択肢が存在しうる
- 非決定性有限オートマトン(NFA)
- NFA では、機会はそれ自体のコピーを複数個作成し、すべての可能性を並列にたどる
- 機械のコピーのどれか 1 つでも受理状態にあれば、NFA は入力文字列を受理する
- 決定性有限オートマトンは DFA という
- 非決定性有限オートマトンの正式な定義
- 非決定性有限オートマトンは 5 個組(Q, Σ, δ, q0, F)である
- Q は状態の有限集合
- Σ は有限のアルファベット
- δ: Q × Σε → P(Q) は遷移関数
- Σεは Σ ∪ {ε} を表す
- P(Q) は Q のすべての部分集合の集まりを表し、べき集合と呼ぶ
- q0 ∈ Q は開始状態
- F ⊆ Q は受理状態の集合
- 等価
- 2 つの機械が同じ言語を認識する時、これらは等価(equivalent)であるという
- NFA と DFA の等価性
- すべての非決定性有限オートマトンは、等価な決定性有限オートマトンを持つ
- 正規表現
- 言語を記述する表現を作成するために、正規表現と呼ばれる正規演算を用いることができる
- 正規表現とそれが記述する言語を区別したい時は、正規表現 R の表現する言語を L(R) と書く
- 正規表現の正式な定義
- R が以下のいずれかであるならば、R は正規表現(regular expression)であるという
- 1: アルファベット Σ に属する a
- 2: ε
- 3: Ø
- 4: R1 と R2 を正規表現として (R1 ∪ R2)
- 5: R1 と R2 を正規表現として (R1 ❍ R2)
- 6: R1 を正規表現として (R1*)
- 項目 1 と 2 は正規表現 a と ε が、それぞれ言語 {a} と {ε} を表すことを意味している
- 項目 3 は正規表現 Ø が空言語を表すことを意味している
- 項目 4・5・6 はそれぞれの表現が、それぞれ言語 R1 と R2 の和集合、連結、および言語 R1 のスターをとることで得られる言語を表すことを意味している
- 一般化非決定性有限オートマトン(GNFA: generalized nondeterministic finite automaton)
- 遷移を表す矢印のラベルとして単にアルファベットの要素やεだけでなく、正規表現も許されるような非決定性有限オートマトン
- GNFA は以下の条件に沿った形式を常に持つ
- 開始状態は他のすべての状態へ遷移する矢印を持つ。しかし他の状態から、開始状態へ遷移する矢印はない
- ただ 1 つの受理状態があって、他のすべての状態から受理状態への矢印がある。しかし、受理状態から出ていく矢印はない。さらに、受理状態は開始状態ではない
- 開始状態と受理状態を除いて、どの 2 つの状態も互いに遷移する矢印を持つ
- GNFA は遷移関数が δ: (Q - {q accept}) × (Q - {q start}) → R という形をしていることを除いて、非決定性有限オートマトンと同じである
- ただし、R はアルファベット Σ 上のすべての正規表現の集まりを表す
- 一般化非決定性有限オートマトンの正式な定義
- 一般化非決定性有限オートマトンは 5 個組(Q, Σ, δ, q start, q accept)である
- Q は状態の有限集合
- Σ は入力アルファベット
- δ: (Q - {q accept}) × (Q - {q start}) → R は遷移関数
- q start は開始状態
- q accept は受理状態
- この節では、有限オートマトンによって認識不可能な言語について考え、有限オートマトンによる言語の認識不可能性の証明方法について説明する
- ポンピング補題(pumping lemma)
- 非正規性の証明に用いられる技法は、従来からポンピング補題と呼ばれる、正規言語に関する定理をもとにしている
- A が正規言語であるならば、ある数 p (ポンピング長)が存在して、s が少なくとも長さ p である A の任意の文字列である時に、s は以下の条件を満たす 3 つの断片 s = xyz に分割できる
- 各 i >= 0 について xy^iz ∈ A
- |y| > 0
- |xy| <= p
- 上記を満たさない場合、その言語は正規ではないことを証明できる
- 第 1 章では有限オートマトンと正規表現という 2 種類の本質的に等価な言語の記述方法を紹介した
- 多くの言語はこの方法で記述できるが、{0^n1^n1 | n >= 0} のようないくつかの単純な言語は記述できないことを示した
- 本章では、より強力な言語記述手法である文脈自由文法(context-free grammar)を与える
- 文法
- 文法は、生成規則(production)とも呼ばれる書き換え規則(substitution rule)の集まりからなる
- A → 0A1 / A → B / B → # のような文法の各行が書き換え規則である
- 文字列は変数と終端記号(terminal)と呼ばれる別の文字から成り立っている
- 1 つの変数が開始変数(start variable)として指定され、本書では、それは先頭の規則の左辺に現れる変数を開始変数とみなすことにする
- 導出
- 文字列を得るための書き換えの列は導出(parse tree)と呼ばれる
- u ⇒ u1 ⇒ ... ⇒ uk ⇒ v ならば、u は v を導出するという
- 文脈自由文法(CFG: context-free grammer)の正式な定義
- 文脈自由文法は、4 個組(V, Σ, R, S)である
- V は変数(variable)と呼ばれる有限集合
- Σ は終端記号(terminal)と呼ばれる、V と共通部分を持たない有限集合
- R は変数(左辺)および変数と終端記号からなる文字列(右辺)で構成される規則(rule)の有限集合
- S ∈ V は開始変数
- 曖昧
- 2 つの異なる構文解析木を持つことを意味する
- 正式な定義
- 文字列 w が 2 つ以上の異なる最左導出を持つならば、その文字列は文脈自由文法 G において曖昧に(ambiguously)導出される。文法 G がある文字列を曖昧に生成するならば、G は曖昧(ambiguous)である
- Chomsky 標準形
- 正式な定義
- すべての規則が以下の形である文脈自由文法を Chomsky 標準形(Chomsky normal form)という
- A → BC
- A → a
- ここで a は任意の終端記号、A は任意の変数、そして B と C は開始変数ではない任意の変数である
- ただし、開始変数 S に対しては、規則 S → ε を加えてもよい
- 少しわかりやすく書くと
- ε規則がない
- 読み換え規則(A → B)がない
- 長文規則の除去
- A → u1u2...un (n >= 3) が長文規則
- プッシュダウン・オートマトン(PDA: pushdown automaton)