形式言語とオートマトン2008 ー第4日目?ー

形式言語とオートマトン2009
ー第6日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
前回までの確認
• 有限オートマトン(FA)
– FAの定義と記述法
テープ上を一方向に動くヘッド
(テープ上の記号を順次読みながら内部状態を遷移)
M = <K, Σ, δ, q0, F> (5つ組)
状態遷移図
様相(configuration)
– FAの種類
決定性FA(DFA)
非決定性FA(ε遷移のあるものとないもの)
– 言語認識能力はどのFAでも同じ。
正規言語(正規表現)を認識
前回までの確認(2)
•
正規表現を認識するFAの存在とその構成法
正規表現αが与えられる。
正規表現αに対して、ε-NFA を構成する。
ε-NFA をDFAに書き換える。
DFAを状態数が最も少ない最簡形のDFA
(Min-DFA)に書き換える。
5. Min-DFAをシミュレートするプログラムを作成する。
1.
2.
3.
4.
(注)上記5の説明および、最簡形DFA存在とその求め方を
与えるMyhill-Nerodeの定理の説明はまだしていません。
前回までの確認(3)
• Pushudown automaton(PDA)
– スタックの定義
データ構造:
・配列(またはアレイ)
・リスト
・スタック
・キュー など
スタックの構造と動作(pop-up と push-down)
LIFO (Last-In First-Out) 型のメモリ
– PDAの定義と記述法
テープ上を一方向に動くヘッド+スタックメモリ
(テープの記号を順次読み、スタック上の記号を順次
読み書きしながら内部状態を遷移)
M = < K, Σ, Γ,δ, q0, Z0, F > (7つ組)
状態遷移図
様相(configuration)
前回までの確認(4)
スタックとPDAのイメージ図
Push down
Pop up
LIFO (Last In First Out)
最後に入れたものが最初に取り出される。
前回までの確認
• Pushdown automaton (PDA)
– PDAの種類
決定性プッシュダウンオートマトン
Deterministic pushdown automaton (DPDA)
非決定性プッシュダウンオートマトン
Nondeterministic pushdown automaton (NPDA)
– 言語認識能力はNPDAの方が高い。
FAは正規言語(正規表現)を認識
NPDAは文脈自由言語を認識
DPDAよりもNPDAの方が言語認識能力大
今日の内容
• チューリングマシン (Turing Machine)
授業ではこの形式のものを扱います
TMの定義
• TM M = < Q, Γ, Σ, δ, q0, B, F > (7つ組)
–
–
–
–
Q:内部状態の集合
Γ:テープ記号の集合
Σ:入力記号の集合 ( Σ⊂ Γ )
δ:状態遷移関数
Q×Γ → Q×Γ×{ L, R }
– q0 :初期状態 ( q0 ∈ Q)
– B:ブランク記号 ( B ∈ Γ – Σ)
– F:最終状態の集合 ( F ⊂ Q )
TMのイメージ図
TM の例
•
•
•
•
•
例4.1(教科書p.90)
例4.2(教科書p.95)
例4.3(教科書p.96)
例4.4(教科書p.100)
例4.5(教科書p.106)
これらを順次確認していきましょう。
例4.1(教科書p.90)
入力文字列
• aa
• aabb
• bbaa
•aaaabbbb
様相(Configuration)の導入
• (q0, a1 a2 a3 ・・・ ai-1 ↓ai ai+1・・・ an )
例4.2(教科書p.95)
M=<Q,Γ,Σ,δ,q0,B,F>
 Q={ q0, q1, q2, q3, qf }
 Σ={ a, b }
 Γ=Σ∪{a’,b’}∪{¢,$,B}
 δ:
δ(q0,a)=(q1,a’,R)
δ(q0,ab’=(q3,b’,R)
δ(q1,a)=(q1,a,R)
δ(q1,b)=(q2,b’,L)
δ(q1,b’)=(q1,b’,R)
δ(q2,a)=(q2,a,L)
δ(q2,a’)=(q0,a’,R)
δ(q2,b’)=(q2,b’,L)
δ(q3,b’)=(q3,b’,R)
δ(q3,$)=(qf,$,L)
例4.3(教科書p.96)
• 言語 { anbnan | n>=1 } を受理するTM
例4.3(教科書p.96)
例4.4(教科書p.100)
• { ww | w ∈ { a, b }+ } を受理するTM
例4.5(教科書p.106)
• 2進数の和を計算するTM
今日はここまで
• 少しずつ復習をしてください。
• 個々のものは決して難しくはありません。
• 引き続き頑張りましょう。