夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

テスト勉強②

勉強

Autómata

今度は形式言語理論、つまりオートマトンとかそこらへんの話題なんですが、そちらをまとめたいと思います。というかメモ書き。数学よりはポテンシャルで殴れそうなんですが^^;

オートマトン

有限オートマトン

具体的な定義は省略。statementとしての意味だけ。

M=(Q,\Sigma ,\delta ,q_0, F)

この時、 Qが空でない状態(state)の有限集合、 \Sigmaは入力アルファベット、 q_0は初期状態、 Fは受理状態のみを含んだ Qの部分集合となっている。そして、 \deltaが状態遷移関係という三項関係の集合で、 (p,a,q)\in \deltaは遷移とよばれてこれによって決定性と非決定性がわかれる。つまり各 p\in Qと各 a\in \Sigmaに対して (p,a,q) \in \deltaとなる状態 qがちょうど一つ存在する時に Mが決定性であるという。そうでない場合は非決定性であるといい、それぞれDFA,NFAと略す。

同一性

DFAとNFAは同一の言語を受理することができる。NFAからDFAは定義から明らかで、DFAからNFAを構成するときのみ証明する必要がある。ここでは証明は省略して構成法だけ紹介する。
NFAを M=(Q,\Sigma ,\delta ,q_0, F)とするとDFAは \tilde{M}=(\tilde{Q},\Sigma ,\tilde{\delta},\tilde{q_0},\tilde{F})と定義できて以下のような条件を満たしている。

  • \tilde{Q}=\{ S \mid S\subseteq Q\}
  • \tilde{q_0}=\{ q_0 \}
  • \tilde{F} = \{ S\subseteq Q \mid S\cap F\neq \phi\}
  • \tilde{\delta}(S,a)=\{ q\in Q\mid \exists p\in S, (p,a,q)\in \delta\}
正則言語・Pumping Lemma

有限オートマトンによって受理される言語を正則言語という。逆は成り立たないが、正則言語は必ず以下のpumping lemmaと呼ばれる定理を満たす。（つまり正則言語であることを示すためにこの定理を用いてはならない。）

L\subseteq \Sigma^{*}を正則言語とする。このときある定数 N\geq 1が存在して、長さが N以上の Lに属する任意の記号列 xにたいして、 xの分解 x=uvwで次の条件を満たすものがある。

  1. 1\leq |v| \leq N
  2. 任意の m\geq 0に対して uv^{m}w\in L
Myhill-Nerodeの定理

言語 L\subseteq \Sigma^{*}に対して以下の三つは同値である。

  1. Lは正則である。
  2. 有限指標で右不変な同値関係 Rが存在して、 Lはその同値類のいくつかの和集合の形に書ける。
  3. R_{L}は有限指標である。

ちなみにここで言う指標とは同値類の個数のことである。この定理を用いて小集合にまとめることで最小オートマトンを構成できる。具体的には M=(Q,\Sigma ,\delta ,q_0 , F)に対し次のアルゴリズムを回した時 UnMarkedListに含まれている状態の組を区別不可能とすることで一つの状態にまとめることで構成できる。

begin
  MarkedList \leftarrow \{ (p,q)\mid p\in F, q\in Q-F\};
  UnMarkedList \leftarrow F\times F\cup (Q-F)\times (Q-F);
  while
    ある記号 a\in\Sigmaとある組(p,q)\in UnMarkedListが存在して(\delta (p,a),\delta (q,a))\in MarkedListとなっている
    then
      begin
         MarkedList\leftarrow\{ (p,q)\}\cup MarkedList;
         UnMarkedList\leftarrow UnMarkedList - \{ (p,q)\};
      end
end

Emptiness Check

決定性有限オートマトン Mに対し、初期状態から幅優先で終状態があるか見ていきその有無によって、 Mを受理するような言語があるかどうかをチェックするアルゴリズム。
有限オートマトンについてのアルゴリズムのいくつかはうまく問題を変形して上のアルゴリズムに適用できる形にかえることで構成できる。

文脈自由文法

文脈自由文法・文脈自由言語

G=(V,T,P,S)
で与えられる。 Vは有限アルファベットで変数の集合、 Tは同じく有限アルファベットで終端記号の集合である。ただし V\cap T=\phiである。 Sは S \in Vで開始記号と呼ばれる。最後に Pは有限個の生成規則の集合である。生成規則は A\in V, \alpha\in (V\cup T)^{*}に対して A\rightarrow\alphaという形をしている。
ある変数から生成規則を何度か繰り返して \alpha\in (V\cup T)^{*}まで到達可能な時これを導出と言う（文字の導入が大変なので少し曖昧な表現にしています。）
そして Sから導出される記号列全体の集合を Gの生成する言語という。このように文脈自由文法から生成された言語が文脈自由言語である。

Chomsky標準形

空語を含まない文脈自由言語 Lは次の形の生成規則しかもたない文脈自由文法によって生成される。
A\rightarrow BC
A\rightarrow a
ただし A,B,Cは変数で aは終端記号である。この形の文脈自由文法をChomsky標準形と呼ぶ。

Pumping Lemma

文脈自由言語にもPumping Lemmaが存在する。取扱い上の注意は正規言語と同様である。

Lを文脈自由言語とする。このとき Lにのみ依存する定数 Nが存在して |x|\geq Nを満たす言語 Lの記号列 zに対して、次の３つの条件を満たす zの分解 z=uvwxyが存在する。

  1. |vx|\geq 1
  2. |vwx|\leq N
  3. すべての n\geq 0に対して uv^{n}wx^{n}y\in Lである。
プッシュダウン・オートマトン

有限オートマトンだと文脈自由言語(CFG)は認識できないものがある。CFGを丁度認識するオートマトンがプッシュダウン・オートマトンである。
プッシュダウン・オートマトンは通常の有限オートマトンにスタックを導入したものとなっている。またわかりやすさのためにスタックの底をしめす特別な記号が用いられることが多い。言語を走査するスタック付きの状態ヘッドで表現される。

チューリングマシン

アラン・チューリングによって導入された計算モデル。
形式的には以下のように定義される。
M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,F)
で Qが有限個の状態の集合、 \Gammaはテープのセルにかくことができる記号であるテープ記号の有限集合、 Bは B\in\Gammaで空白記号、 \Sigmaは \Gammaの空白記号を含まない部分集合、 \deltaは Q\times\Gamma\rightarrow Q\times\Gamma\times\{ L,R\}の部分関数、 q_0は初期状態、 Fは受理状態の集合である（つまり Qのサブセット）

右方向に無限に長いテープがあって、それを読み込むヘッドが有限制御部に従ってテープの内容を書き換えながら左右に１セルずつ移動することによって動作する。入力記号列は左詰めで与えられ、残りのテープには空白記号が書かれている。

順次更新します。