テスト勉強②
今度は形式言語理論、つまりオートマトンとかそこらへんの話題なんですが、そちらをまとめたいと思います。というかメモ書き。数学よりはポテンシャルで殴れそうなんですが^^;
オートマトン
有限オートマトン
具体的な定義は省略。statementとしての意味だけ。
この時、が空でない状態(state)の有限集合、は入力アルファベット、は初期状態、は受理状態のみを含んだの部分集合となっている。そして、が状態遷移関係という三項関係の集合で、は遷移とよばれてこれによって決定性と非決定性がわかれる。つまり各と各に対してとなる状態がちょうど一つ存在する時にが決定性であるという。そうでない場合は非決定性であるといい、それぞれDFA,NFAと略す。
同一性
DFAとNFAは同一の言語を受理することができる。NFAからDFAは定義から明らかで、DFAからNFAを構成するときのみ証明する必要がある。ここでは証明は省略して構成法だけ紹介する。
NFAをとするとDFAはと定義できて以下のような条件を満たしている。
正則言語・Pumping Lemma
有限オートマトンによって受理される言語を正則言語という。逆は成り立たないが、正則言語は必ず以下のpumping lemmaと呼ばれる定理を満たす。(つまり正則言語であることを示すためにこの定理を用いてはならない。)
を正則言語とする。このときある定数が存在して、長さが以上のに属する任意の記号列にたいして、の分解で次の条件を満たすものがある。
- 任意のに対して
文脈自由文法
文脈自由文法・文脈自由言語
で与えられる。は有限アルファベットで変数の集合、は同じく有限アルファベットで終端記号の集合である。ただしである。はで開始記号と呼ばれる。最後には有限個の生成規則の集合である。生成規則はに対してという形をしている。
ある変数から生成規則を何度か繰り返してまで到達可能な時これを導出と言う(文字の導入が大変なので少し曖昧な表現にしています。)
そしてから導出される記号列全体の集合をの生成する言語という。このように文脈自由文法から生成された言語が文脈自由言語である。
Chomsky標準形
空語を含まない文脈自由言語は次の形の生成規則しかもたない文脈自由文法によって生成される。
ただしは変数では終端記号である。この形の文脈自由文法をChomsky標準形と呼ぶ。
Pumping Lemma
文脈自由言語にもPumping Lemmaが存在する。取扱い上の注意は正規言語と同様である。
を文脈自由言語とする。このときにのみ依存する定数が存在してを満たす言語の記号列に対して、次の3つの条件を満たすの分解が存在する。
- すべてのに対してである。
チューリングマシン
アラン・チューリングによって導入された計算モデル。
形式的には以下のように定義される。
でが有限個の状態の集合、はテープのセルにかくことができる記号であるテープ記号の有限集合、はで空白記号、はの空白記号を含まない部分集合、はの部分関数、は初期状態、は受理状態の集合である(つまりのサブセット)
右方向に無限に長いテープがあって、それを読み込むヘッドが有限制御部に従ってテープの内容を書き換えながら左右に1セルずつ移動することによって動作する。入力記号列は左詰めで与えられ、残りのテープには空白記号が書かれている。
順次更新します。