計算理論の基礎 オートマトンと言語 読書ノート

『計算理論の基礎 原著第2版』の読書ノート。

方針

実はしばらく前に少し読んだのだが、その時は正規言語の途中までやって放置してしまった。今回改めて読み進めるにあたっての方針として、以下を挙げる。

  • 演習問題はできる限り自力で解く
  • 定理と証明は書き写す

進捗

  • 2021/11/06: 開始

第0章 / 序論

  • オートマトン、計算可能性、複雑さのついての教科書
    • 計算機の本質的な能力とその限界は何か？
  • 計算問題には優しい問題と難しい問題がある
    • ソーティング問題 … 優しい
    • スケジューリング問題 … 難しい
  • 何が、問題の難しさ・やさしさを決めているのだろうか？
    • いまだに明確な答えが得られていない
  • 計算の困難さに基づいて問題を分類するうまい方法の発見
    • 計算が難しいことの証拠を示すことができる
  • 計算が困難な問題の対処
    • 難しさの根源がどこにあるか
    • 難しい部分の変更によって解決
    • 完全な解を諦めることで解決
  • 初期の暗号
    • 問題は難しいものより簡単な方が望ましい
    • 暗号は難しいほうが望ましい
  • 計算可能性の理論
    • 計算機の理論的モデル
  • オートマトン理論
    • 計算の数学的モデル

第1章 / 正規言語

  • 計算のモデル（computational model）
    • 有限オートマトン（finite automaton）
  • Markov連鎖（Markov chain）
    • 有限オートマトンに確率的要素を許す
    • パターンの認識を試みる際に有益
    • 音声処理、光学的文字認識、価格変動のモデル化・予測
  • 有限オートマトンの状態遷移図
    • 開始状態（start state）、受理状態（accept state）、遷移（transition）
    • 入力を処理し、その出力は受理（accept）または拒否（reject）のいずれか一方
  • 有限オートマトンの正式な定義
    • 有限オートマトンは以下の5個のもののリスト
      • 状態の集合
      • 入力アルファベット
      • 動作規則
      • 開始状態
      • 受理状態
    • 動作規則 … $\delta$ で表される遷移関数を用いる
      • オートマトンが状態 $x$ にあって $1$ を読み出したときに状態 $y$ へ移る = $\delta(x, 1) = y$

定義1.5

有限オートマトン（finite automaton）は5個組（ $Q, \Sigma, \delta, q_0, F$ ）である。ここで、

  1. $Q$ は状態（state）と呼ばれる有限集合
  2. $\Sigma$ はアルファベット（alphabet）と呼ばれる有限集合
  3. $\delta : Q \times \Sigma \longrightarrow Q$ は遷移関数（transition function）
  4. $q_0 \in Q$ は開始状態（start state）
  5. $F \subseteq Q$ は受理状態の集合（set of accept states）
  • 言語
    • $A$ を、機械 $M$ が受理するすべての文字列の集合とするならば、 $A$ は機械 $M$ の言語（language of machine M）であるといい、 $L(M) = A$ と書く
    • $M$ は $A$ を認識する（M recognizes A）
    • 機械は、つねに唯一つの言語を認識する
      • 文字列を一つも受理しない場合、 $\emptyset$ （空言語） を認識する
  • 有限オートマトンの計算
    • $M = (Q, \Sigma, \delta, q_0, F)$ を有限オートマトンとし、 $w = w_1w_2 \cdots w_n$ は文字列で、各 $w_i$ はアルファベット $\Sigma$ の要素とする。以下の三条件をみたす状態の列 $r_0, r_1, \ldots , r_n \in Q$ が存在するならば、 $M$ は $w$ を受理する（accept）という。
      • $r_0 = q_0$
      • $i = 0, \ldots , n - 1$ のとき、 $\delta(r_i, w_{i + 1}) = r_{i + 1}$
      • $r_n \in F$

定義1.16

ある有限オートマトンで認識される言語を正規言語（regular language）という。

  • 正規演算（regular operation）
    • 言語を操作するために特別に設計された演算

定義1.23

$A$ と $B$ を言語とする。正規演算とは、以下のように定義された和集合演算（union）、連結演算（concatenation）、スター演算（star）のいずれかである。

  • 和集合演算: $A \cup B = \lbrace x \mid x \in A \lor x \in B \rbrace$
  • 連結演算: $A \circ B = \lbrace xy \mid x \in A \land x \in B \rbrace$
  • スター演算: $A^{*} = \lbrace x_1x_2 \ldots x_k \mid k \geq 0 \land x_i \in A \rbrace$

定理1.25

正規言語のクラスは、和集合演算に関して閉じている。

言い換えれば、 $A_1$ と $a_2$ が正規言語であれば、 $A_1 \cup A_2$ も正規言語である。

  • $A_1$ と $A_2$ が正規なので、 $A_1$ を認識するある有限オートマトン $M_1$ と、 $A_2$ を認識するある有限オートマトン $M_2$ がある
    • 実際に $M_1$ と $M_2$ から $M$ を構成することによって証明
    • $M_1$ と $M_2$ をシミュレートし、どちらかのシミュレーションが受理すれば $M$ としても受理する
    • $M_1$ と $M_2$ の状態の対を $M$ の状態として、同時にシミュレート

証明

$M_1$ は $A_1$ を認識し、 $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ であり、 $M_2$ は $A_2$ を認識し、 $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ とする。

  1. $Q = \lbrace (r_1, r_2) \mid r_1 \in Q_1 \land r_2 \in Q_2 \rbrace$ とする。これは $Q_1, Q_2$ のCartesian積であり、 $Q_1 \times Q_2$ と表す。
  2. アルファベット $\Sigma$ は、 $M_1, M_2$ のアルファベットと同じである。異なるアルファベットを持つ場合は $\Sigma = \Sigma_1 \cup \Sigma_2$ とすればよい。
  3. 遷移関数 $\delta$ は、以下のように定義される。各 $(r_1, r_2) \in Q$ と各 $a \in \Sigma$ に対して、 $\delta((r_1, r_2), a) = (\delta_1(r_1, a), \delta_2(r_2, a))$ とする。
  4. $q_0$ は 対 $q_1, q_2$ である。
  5. $F$ は、対の一方が $M_1$ または $M_2$ の受理状態であるような対の集合である。この集合は、$$F = \lbrace (r_1, r_2) \mid r_1 \in F_1 \lor r_2 \in F_2 \rbrace$$ と表される。
2021-11-06