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

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

前回までの確認（２） 正規表現を認識するFAの存在とその構成法 正規表現αが与えられる。 正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数最少のDFAに書き換える。 Min-DFAをシミュレートするプログラムを作成する。

確認問題集 （少しずつこなしていってください。）

確認問題１ （オートマトンの定義） 次の状態遷移図で与えられるオートマトンを、　M=＜K,Σ,δ,q0, F＞ の５つ組で記述しなさい。 p q r a b

確認問題 前問のオートマトンの動作のトレース 次の文字列のうち、前問のオートマトンMが 受理するのはどれとどれですか？ aabba bababbb aaaa bbba

確認問題 下図のε-NFAをDFAに書き換えなさい。 a ４ b b ε ε ε a １ ２ ３ ６ ７ ８ b ５ c c ε

確認問題 DFAからmin-DFAを求める手順について 述べなさい。 （理論的根拠は、後日お話します。Myhill-Nerodeの定理がポイントになりす。）

確認問題 （正規表現を受理するmin-DFAを求める） 次の正規表現を受理するmin-DFAを求めよ。 (ab|bc)*a(b|c) (a|b|ε)(ab|b)*bc (a|b)*a(a|b)

さて、…

今日の話題 FAの様相(configuration) (第2章の補足) プッシュダウンオートマトン （pushdown automaton） （第3章の話）

FAの様相 FAの動作の様子・状況を様相(configuration)という。 動作開始時の様相を特に、初期様相という。

様相の表現 入力文字列 入力文字列の末尾

様相表現の例 （具体例で理解しよう） 教科書p.36 問2.1

FA M = <K, Σ, δ, q0, F> 1 p q r

FA M = <K, Σ, δ, q0, F> q p r 1 1 p q r 様相(p, 11010) |- (q,1010) |- (q,010) |- (q,10) |- (q, 0) |- (q, ε) (p,11010) |*- (q,ε) <= Mは入力文字列 11010 を受理

様相(configuration)という用語は、本を読んでいると時々出てきます。 オートマトンの動作状況を表現する単なる １つの方法にすぎません。 でも、便利ですよね。

自主練習 教科書p.58の【演習問題】にチャレンジしてください。

Let’s get down to today’s topics. ここから新しい話し Let’s get down to today’s topics. （第３章に入ります）

プッシュダウンオートマトン 有限オートマトンにプッシュダウンスタックメモリを追加装備したもの。 Pushdown automaton (PDA)

プッシュダウンスタック 歴史的view: 初期の頃：プッシュダウン型スタックメモリ （特殊なハードウェアと考えていた） 現在：「スタック」は基本的なデータ構造の１つと考えられている。プッシュダウンスタックとは言わず、スタックと呼ぶことが多い。 データ構造： ・配列（またはアレイ） ・リスト ・スタック ・キュー　など 続きは「データ構造とアルゴリズム」で。

プッシュダウンスタックのイメージ Pop up Push down LIFO (Last In First Out) 最後に入れたものが最初に取り出される。

PDAの種類 決定性プッシュダウンオートマトン 非決定性プッシュダウンオートマトン Deterministic pushdown automaton (DPDA) 非決定性プッシュダウンオートマトン Nondeterministic pushdown automaton (NPDA)

DPDA M の定義 M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合 （#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K )

DPDA M の定義 M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合 （#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K )

ハードウェア構成でのイメージ

DFA と DPDA 類似点と相違点 類似点： 相違点： ・入力テープ ・プッシュダウンスタックメモリ （左から右へ読み込むだけ） 類似点： 相違点： ・入力テープ ・プッシュダウンスタックメモリ 　（左から右へ読み込むだけ） ・ヘッドとその内部状態

研究 　　ハードウェア構成でのイメージ なぜ、プッシュダウンスタック？

研究テーマ 内部処理装置 記憶装置 入力記号列

参考図書 J. ライバー，認知科学への招待 チューリングとウィトゲンシュタインを道しるべに，新曜社，今井邦彦訳(1994). 研究課題：　脳の設計図を記述せよ。 事実を言葉で表現し，列挙せよ。 UMLで表記せよ。 SysMLで表記せよ。 プログラミング言語で表現せよ。

難しいことはさておいて… (例を見てみましょう) 教科書p.68例3.1

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

δ：状態遷移関数 K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) δ( q0, b, A ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 )

DPDA M の例 M = <K,Σ,Γ,δ,q0,Z0, F> δ( q0, a, Z0 ) ( q0, AZ0 ) 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 ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 )

動作のトレース (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, ε, Z0 ) ( q2, Z0 ) 受理 拒否

状態遷移図

動作のトレース 自分で確認しよう K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 ) (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) |- (q１, ε, AZ0) 受理 拒否

練習 教科書のp.71 問題3.1の DPDA の動作を いろいろな入力に対して調べてみよう。

非決定性プッシュダウンオートマトン DPDAでの状態遷移関数部分が １対多の写像になる。

DPDA M の定義（再） M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合 （#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K )

NPDA M の定義（再） M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合 （#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → ２K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K )

DPDA M の例 M = <K, Σ, Γ, δ, q0, Z0, F> （教科書p.73の例3.2）

NPDA M の例 M = <K,Σ,Γ,δ,q0,Z0, F> K×Γ* δ( q0, a, Z0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) (q1,ε), (q3,A) δ( q1, b, A) ( q1,ε) δ( q1, c, Z0) ( q2, Z0 ) δ( q2, c, Z0) δ( q2,ε, Z0) ( qf, Z0 ) δ( q3, b, A ) ( q3,A ) δ( q3, c, A ) ( q4,ε) δ( q4, c, A ) δ( q4,ε, Z0) ( qf, Z0 ) M = <K,Σ,Γ,δ,q0,Z0, F> K = {q0,q1,q2, q3, q4, qf } Σ = { a, b, c } Γ = { A, Z0 } δ：状態遷移関数 q0 ：初期状態 Z0：ボトムマーカ F = { qf }⊂ K

状態遷移図

今日の設問（１番だけ提出） (q0, aaabbbcc, Z0) |*- ? aabbbccc は受理されるか？

ここまでのまとめ プッシュダウンスタック プッシュダウンオートマトン 決定性 非決定性 PDAはFAを含む（PDAはFAよりも文字列認識能力は高い。）　＜＝（Why?） DPDA は NPDA よりも能力は低い。 （証明はしませんが、事実です。）

次回は、チューリングマシンです。 チューリングマシンは、アルゴリズムや計算に関する理論の基礎を与えてくれます。 チューリングマシンと、認識可能な言語との対応（チョムスキー階層）の話しもやがて出てきます（第５章）。 線形拘束オートマトン（線形有界オートマトン）も今後導入します。 計算量・計算の複雑さなどの話題にも触れましょう。　　お楽しみに！

ここまで積み残してきているもの Myhill-Nerodeの定理 （DFAにおける）ポンピング補題　など