形式言語とオートマトン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 今日はここまで • 少しずつ復習をしてください。 • 個々のものは決して難しくはありません。 • 引き続き頑張りましょう。
© Copyright 2024 ExpyDoc