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