形式言語とオートマトン2009 ー第６日目ー東京工科大学コンピュータサイエンス学部亀田弘之前回までの確認 • 有限オートマトン(FA) – FAの定義と記述法 テープ上を一方向に動くヘッド（テープ上の記号を順次読みながら内部状態を遷移） M = <K, Σ, δ, q0, F> （５つ組） 状態遷移図 様相（configuration） – FAの種類 決定性FA（DFA） 非決定性FA（ε遷移のあるものとないもの） – 言語認識能力はどのFAでも同じ。 正規言語（正規表現）を認識前回までの確認（２） • 正規表現を認識するFAの存在とその構成法正規表現αが与えられる。正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数が最も少ない最簡形のDFA (Min-DFA)に書き換える。 5. Min-DFAをシミュレートするプログラムを作成する。 1. 2. 3. 4. （注）上記５の説明および、最簡形DFA存在とその求め方を与えるMyhill-Nerodeの定理の説明はまだしていません。前回までの確認（３） • Pushudown automaton(PDA) – スタックの定義データ構造：・配列（またはアレイ）・リスト・スタック・キューなど スタックの構造と動作（pop-up と push-down） LIFO (Last-In First-Out) 型のメモリ – PDAの定義と記述法 テープ上を一方向に動くヘッド＋スタックメモリ（テープの記号を順次読み、スタック上の記号を順次読み書きしながら内部状態を遷移） M = < K, Σ, Γ,δ, q0, Z0, F > （７つ組） 状態遷移図 様相（configuration）前回までの確認（４）スタックと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 今日はここまで • 少しずつ復習をしてください。 • 個々のものは決して難しくはありません。 • 引き続き頑張りましょう。