東京工科大学 コンピュータサイエンス学部 亀田弘之 形式言語とオートマトン2011 ー第8日目ー 東京工科大学 コンピュータサイエンス学部 亀田弘之

前回までの確認 有限オートマトン(FA) FAの定義と記述法 FAの種類 言語認識能力はどのFAでも同じ。 テープ上を一方向に動くヘッド （テープ上の記号を順次読みながら内部状態を遷移） M = <K, Σ, δ, q0, F> 　（５つ組） 状態遷移図 様相（configuration） FAの種類 決定性FA（DFA） 非決定性FA（ε遷移のあるものとないもの） 言語認識能力はどのFAでも同じ。 正規言語（正規表現）を認識

有限オートマトンのイメージ(1) qk FAの概観 a1 a2 ai-1 ai an セル 入力記号 入力テープ ヘッド 内部状態 ・・・

有限オートマトンのイメージ(2) FA = ( K, Σ, δ, q0, F ) ただし、 K ： 状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

有限オートマトンのイメージ(2’) K = { r, s, t} , Σ= { a, b }, q0 = r, F ={ t }, δ ： δ ：　 状態 入力 次の状態 r a s b t

有限オートマトンのイメージ(3) s a a b r b t a b

前回までの確認（２） 正規表現を認識するFAの存在とその構成法 正規表現αが与えられる。 正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数が最も少ない最簡形のDFA (Min-DFA)に書き換える。 Min-DFAをシミュレートするプログラムを作成する。 （注）上記５の説明および、最簡形DFA存在とその求め方を 　　　与えるMyhill-Nerodeの定理の説明はまだしていません。

前回までの確認（３） Pushudown automaton(PDA) スタックの定義 PDAの定義と記述法 データ構造： ・配列（またはアレイ） ・リスト ・スタック ・キュー　など Pushudown automaton(PDA) スタックの定義 スタックの構造と動作（pop-up と push-down） LIFO (Last-In First-Out) 型のメモリ PDAの定義と記述法 テープ上を一方向に動くヘッド＋スタックメモリ （テープの記号を順次読み、スタック上の記号を順次 　読み書きしながら内部状態を遷移） M = < K, Σ, Γ,δ, q0, Z0, F > 　（７つ組） 状態遷移図 様相（configuration）

前回までの確認（４） スタックとPDAのイメージ図 Pop up Push down LIFO (Last In First Out) 最後に入れたものが最初に取り出される。

PDAのイメージ

前回までの確認 Pushdown automaton (PDA) PDAの種類 言語認識能力はNPDAの方が高い。 決定性プッシュダウンオートマトン 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.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

今日はここまで 少しずつ復習をしてください。 個々のものは決して難しくはありません。 引き続き頑張りましょう。 来週は少し難しいです。 来週は授業評価アンケートを取りますので、PCを持参してください。