形式言語とオートマトン2010 ー第6日目ー東京工科大学コンピュータサイエンス学部亀田弘之前回までの確認 • 有限オートマトン(FA) – FAの定義と記述法 テープ上を一方向に動くヘッド（テープ上の記号を読みながら、内部状態を変えていく） M = <K, Σ, δ, q0, F> 状態遷移図 – FAの種類 決定性FA（DFA） 非決定性FA（ε遷移のあるものとないもの） – 言語認識能力はどのFAでも同じ。 正規言語（正規表現）を認識可能。 2 前回までの確認（２） • 正規表現を認識するFAの存在とその構成法 1. 2. 3. 4. 5. 正規表現αが与えられる。正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数最少のDFAに書き換える。 Min-DFAをシミュレートするプログラムを作成する。（参考文献[1]参照） 3 確認問題集 • （少しずつこなしていってください。） 4 確認問題１ • （オートマトンの定義）次の状態遷移図で与えられるオートマトンを、 M=＜K,Σ,δ,q0, F＞の５つ組で記述しなさい。 a p b a q a b r b 5 確認問題 • 前問のオートマトンの動作のトレース – 次の文字列のうち、前問のオートマトンMが受理するのはどれとどれですか？ ① ② ③ ④ aabba bababbb aaaa bbba 6 確認問題 • 下図のε-NFAをDFAに書き換えなさい。４ b a １ ε ε ２３５ c b b ε ６ a ７８ c ε 7 確認問題 • DFAからmin-DFAを求める手順について述べなさい。（理論的根拠は、後日お話します。MyhillNerodeの定理がポイントになりす。） 8 確認問題 • （正規表現を受理するmin-DFAを求める）次の正規表現を受理するmin-DFAを求めよ。 1. (ab|bc)*a(b|c) 2. (a|b|ε)(ab|b)*bc 3. (a|b)*a(a|b) 9 さて、… 10 今日の話題 1. FAの様相(configuration) (第2章の補足) 2. プッシュダウンオートマトン（pushdown automaton）（第3章の話） 11 FAの様相 • FAの動作の様子・状況を様相(configuration) という。 • 動作開始時の様相を特に、初期様相という。 12 様相の表現入力文字列入力文字列の末尾 13 様相表現の例 • （具体例で理解しよう）教科書p.36 問2.1 14 FA M = <K, Σ, δ, q0, F> 0 1 q 0 1 p 0 r 1 15 FA M = <K, Σ, δ, q0, F> 0 1 q 0 1 p 0 r 1 様相(p, 11010) |- (q,1010) |- (q,010) |- (q,10) |- (q, 0) |- (q, ε) (p,11010) |*- (q,ε) <= Mは入力文字列 11010 を受理 16 • 様相(configuration)という用語は、本を読んでいると時々出てきます。 • オートマトンの動作状況を表現する単なる１つの方法にすぎません。でも、便利ですよね。 17 ここから新しい話し • （第３章に入ります） Let’s get down to today’s topics. 18 プッシュダウンオートマトン • 有限オートマトンにプッシュダウンスタックメモリを追加装備したもの。 • Pushdown automaton (PDA) 19 プッシュダウンスタック • 歴史的view: – 初期の頃：プッシュダウン型スタックメモリ（特殊なハードウェアと考えていた） – 現在：「スタック」は基本的なデータ構造の１つと考えられている。プッシュダウンスタックとは言わず、スタックといわれることが多い。データ構造：・配列（またはアレイ）・リスト続きは「データ構造とアルゴリズム」で。・スタック・キューなど 20 プッシュダウンスタックのイメージ Push down Pop up LIFO (Last In First Out) 最後に入れたものが最初に取り出される。 21 PDAの種類 • 決定性プッシュダウンオートマトン Deterministic pushdown automaton (DPDA) • 非決定性プッシュダウンオートマトン Nondeterministic pushdown automaton (NPDA) 22 DPDA M の定義 • M = <K, Σ, Γ, δ, q0, Z0, F> – K:内部状態の集合（#K < ∞） – Σ：入力アルファベット（#Σ < ∞） – Γ：プッシュダウンアルファベット（#Γ < ∞） – δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* – q0：初期状態 (q0 ∈K ) – Z0：ボトムマーカ ( Z0∈Γ) – F：最終状態 ( F ⊂ K ) 23 DPDA M の定義 • M = <K, Σ, Γ, δ, q0, Z0, F> – K:内部状態の集合（#K < ∞） – Σ：入力アルファベット（#Σ < ∞） – Γ：プッシュダウンアルファベット（#Γ < ∞） – δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* – q0：初期状態 (q0 ∈K ) – Z0：ボトムマーカ ( Z0∈Γ) – F：最終状態 ( F ⊂ K ) 24 ハードウェア構成でのイメージ 25 DFA と DPDA 類似点と相違点類似点：相違点：・入力テープ・プッシュダウンスタックメモリ（左から右へ読み込むだけ）・ヘッドとその内部状態 26 研究ハードウェア構成でのイメージなぜ、プッシュダウンスタック？ 27 難しいことはさておいて… • (例を見てみましょう) 教科書p.68例3.1 28 DPDA M の例 • M = <K, Σ, Γ, δ, q0, Z0, F> – K内部状態の集合 = { q0, q1, q2 } （#K < ∞） – Σ入力アルファベット = { a, b } （#Σ < ∞） – Γプッシュダウンアルファベット = { A, Z0 }（#Γ< ∞） – δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* – q0 初期状態 = q0 (q0 ∈K ) – Z0：ボトムマーカ ( Z0∈Γ) – F：最終状態 F = { q2 } ⊂ K 29 δ：状態遷移関数 K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q 1, ε ) δ( q1, b, A ) ( q 1, ε ) δ( q1, ε, Z0 ) ( q2, Z0 ) 30 DPDA M の例 • M= <K,Σ,Γ,δ,q0,Z0, F> – – – – – – – K = { q0, q1, q2 } Σ = { a, b } Γ = { A, Z0 } δ：状態遷移関数 q0 ：初期期状態 Z0：ボトムマーカ F = { q2 }⊂ K K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q 1, ε ) δ( q1, b, A ) ( q 1, ε ) δ( q1, ε, Z0 ) ( q2, Z0 ) 31 動作のトレース • (q0, aaabbb, Z0) |- (q0, aabbb, AZ0) |- (q0, abbb, AAZ0) |- (q0, bbb, AAAZ0) |- (q1, bb, AAZ0) |- (q1, b, AZ0) |- (q1, ε, Z0) |- (q2, ε, Z0) 受理 • |- (q0, aab, Z0) |- (q0, ab, AZ0) |- (q0, b, AAZ0) |- (q0, ε, AZ0) 拒否 K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q 1, ε ) δ( q1, b, A ) ( q 1, ε ) δ( q1, ε, Z0 ) ( q2, Z0 ) 32 状態遷移図 33 動作のトレース • (q0, aaabbb, Z0) |- (q0, aabbb, AZ0) |- (q0, abbb, AAZ0) |- (q0, bbb, AAAZ0) |- (q1, bb, AAZ0) |- (q1, b, AZ0) |- (q1, ε, Z0) |- (q2, ε, Z0) 受理 • |- (q0, aab, Z0) |- (q0, ab, AZ0) |- (q0, b, AAZ0) |- (q0, ε, AZ0) 拒否自分で確認しよう K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q1, ε ) δ( q1, b, A ) ( q1, ε ) δ( q1, ε, Z0 ) ( q2, Z0 ) 34 練習 • 教科書のp.71 問題3.1の DPDA の動作をいろいろな入力に対して調べてみよう。 35 非決定性プッシュダウンオートマトン • DPDAでの状態遷移関数部分が１対多の写像になる。 36 DPDA M の定義（再） • M = <K, Σ, Γ, δ, q0, Z0, F> – K:内部状態の集合（#K < ∞） – Σ：入力アルファベット（#Σ < ∞） – Γ：プッシュダウンアルファベット（#Γ < ∞） – δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* – q0：初期状態 (q0 ∈K ) – Z0：ボトムマーカ ( Z0∈Γ) – F：最終状態 ( F ⊂ K ) 37 NPDA M の定義（再） • M = <K, Σ, Γ, δ, q0, Z0, F> – K:内部状態の集合（#K < ∞） – Σ：入力アルファベット（#Σ < ∞） – Γ：プッシュダウンアルファベット（#Γ < ∞） – δ：状態遷移関数 K×(Σ∪{ε})×Γ → ２K×Γ* – q0：初期状態 (q0 ∈K ) – Z0：ボトムマーカ ( Z0∈Γ) – F：最終状態 ( F ⊂ K ) 38 DPDA M の例 • M = <K, Σ, Γ, δ, q0, Z0, F> （教科書p.73の例3.2） 39 NPDA M の例 K×(Σ∪{ε})×Γ • M= <K,Σ,Γ,δ,q0,Z0, F> – – – – – – – K = {q0,q1,q2, q3, q4, qf } Σ = { a, b, c } Γ = { A, Z0 } δ：状態遷移関数 q0 ：初期状態 Z0：ボトムマーカ F = { qf }⊂ K δ( q0, a, Z0 ) δ( q0, a, A ) δ( q0, b, A ) K×Γ* ( q0, A Z0 ) ( q0, AA ) (q1,ε), (q3,A) δ( q1, b, A) δ( q1, c, Z0) δ( q2, c, Z0) ( q1,ε) ( q2, Z0 ) ( q2, Z0 ) δ( q2,ε, Z0) δ( q3, b, A ) δ( q3, c, A ) δ( q4, c, A ) ( qf, Z0 ) ( q3,A ) ( q4,ε) ( q4,ε) δ( q4,ε, Z0) ( qf, Z0 ) 40 状態遷移図 41 練習問題 1. (q0, aaabbbcc, Z0) |*- ? 2. aaabbbcc は受理されるか？される場合は、その動作の様子を様相表現で示しなさい。 3. aabbbccc は受理されるか？ 42 ここまでのまとめ • プッシュダウンスタック • プッシュダウンオートマトン – 決定性 – 非決定性 • PDAはFAを含む（PDAはFAよりも文字列認識能力は高い。）＜＝（Why?） • DPDA は NPDA よりも能力は低い。（証明はしませんが、事実です。） 43 次回は、チューリングマシンです。 • チューリングマシンは、アルゴリズムや計算に関する理論の基礎を与えてくれます。 • チューリングマシンと、認識可能な言語との対応（チョムスキー階層）の話しもやがて出てきます（第５章）。 • 線形拘束オートマトン（線形有界オートマトン）も今後導入します。 • 計算量・計算の複雑さなどの話題にも触れましょう。お楽しみに！ 44