東京工科大学 コンピュータサイエンス学部 亀田弘之 形式言語とオートマトン2017 ー第6日目ー 東京工科大学 コンピュータサイエンス学部 亀田弘之 佳境に入ってきました！

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

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 前回までの確認（２） 正規表現を認識するFAの存在とその構成法 正規表現αが与えられる。 正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数最少のDFAに書き換える。 Min-DFAをシミュレートするプログラムを作成する。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 前回までに取り組んだ課題 正規表現 α ＝ a(a|b)*bb で定義される言語を受理するDFAを求める。 まず、αと等価なε-NFAを書きだす。 そのε-NFAと等価なDFAを作る。 得られたDFAをもとに、そのDFAと等価であり、かつ、状態数が最少となっているDFAを求める。　 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 確認問題集 （注） 今日もみんなで問題を解きながら、 理解を深めましょう。(Learn by doing.) 周りの人と教え合ってください。(Learn by teaching.) 答えを教える、答えを聞くのではなく、 しっかりと理解しましょう。(Figure it out!) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 前回宿題？ 今日のポイント a f g h d b e c 1 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 確認問題１ （オートマトンの定義） 次の状態遷移図で与えられるオートマトンを、　M1=＜K,Σ,δ,q0, F＞ の５つ組で記述しなさい。 p q r a b 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 確認問題２ 前問のオートマトンの動作のトレース 次の文字列のうち、前問のオートマトンM1が 受理するのはどれですか？ aabba bababbb aaaa bbba abbaabba 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 確認問題３ 下図のε-NFAをDFAに書き換えなさい。 a ４ b b ε ε ε a １ ２ ３ ６ ７ ８ b ５ c c ε 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 確認問題４ DFAからmin-DFAを求める手順について 述べなさい。 （理論的根拠は、述べなくても良い。） 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 確認問題５ （正規表現を受理するmin-DFAを求める） 　　次の正規表現を受理するmin-DFAを求めよ。 (ab|bc)*a(b|c) (a|b|ε)(ab|b)*bc (a|b)*a(a|b) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 さて、… 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 今日からの話題 FAの様相(configuration) (第2章の補足) 演習 プッシュダウンオートマトン （pushdown automaton） （第3章の話） 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 FAの様相 今日のポイント FAの動作の様子・状況を様相(configuration)という。 動作開始時の様相を特に、初期様相という。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 様相の表現 入力文字列 入力文字列の末尾 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 様相表現の例 （具体例で理解しよう） 教科書p.36 問2.1 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 FA M = <K, Σ, δ, q0, F> 1 p q r 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 FA M = <K, Σ, δ, q0, F> 1 p q r 様相(p, 11010) |- (q,1010) |- (q,010) |- (q,10) |- (q, 0) |- (q, ε) (p,11010) |*- (q,ε) <= Mは入力文字列 11010 を受理 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 様相に関するコメント 様相(configuration)という用語は、本を読んでいると時々出てきます。例えば、「様相論理学」。この英語はModal Logic。 混乱しないように！ オートマトンの動作状況を 表現する方法の１つに すぎません。 でも、便利ですよね。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 自主練習 教科書p.58の【演習問題】にチャレンジしてください。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 以上で有限オートマトンは終わり。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 自分の課題を見つけよう。 まずは、議論をする。 議題： この授業をうけ、ここまでに学んだことは何か？　 （単語だけでもいいので多く書き出すこと） 成果物： 自分が理解していない用語（概念）や事実（内容）のうち、最も重要だと思うものを１つ書きだす。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

２．課題 次のε-NFAと等価な状態数最少のDFAを求めよ。 M = { 状態の集合Q, 入力アルファベットS, 状態遷移関数δ, 　　　 初期状態σ, 最終状態の集合F　｝ ただし、 　・Q = { 1, 2, 3 } 　・S = { a, b } 　・σ = 1 　・F = { 1 } 　・δ: δ(1,b)={2}, δ(1,ε)={3}, δ(2,a)={2, 3}, δ(2,b)={3}, δ(3,a)={1} a b ε 1 ー ２ ３ 2 ２，３ 3 １ 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 ヒント 状態遷移図を書く。 等価なDFAを求める。 状態数最少のDFAを求める。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

ここから新しい話し （第３章に入ります） Let’s get down to today’s topics. 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 プッシュダウンオートマトン 今日のポイント 有限オートマトンにプッシュダウンスタックメモリを追加装備したもの。 Pushdown automaton (PDA) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 プッシュダウンスタック 歴史的概観: 初期の頃：プッシュダウン型スタックメモリ （特殊なハードウェアと考えていた） 現在：「スタック」は基本的なデータ構造の１つと考えられている。プッシュダウンスタックとは言わず、スタックと呼ぶことが多い。 データ構造： ・配列（またはアレイ） ・リスト ・スタック ・キュー　など 続きは「データ構造とアルゴリズム」で。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 プッシュダウンスタックのイメージ Pop up Push down LIFO (Last In First Out) 最後に入れたものが最初に取り出される。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 PDAの種類 決定性プッシュダウンオートマトン Deterministic pushdown automaton (DPDA) 非決定性プッシュダウンオートマトン Nondeterministic pushdown automaton (NPDA) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 DPDA M の定義 M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合　（#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K ) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 DPDA M の定義 M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合　（#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K ) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 ハードウェア構成でのイメージ 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 DFA と DPDA 類似点と相違点 類似点： 相違点： ・入力テープ ・プッシュダウンスタックメモリ 　（左から右へ読み込むだけ） ・ヘッドとその内部状態 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 研究 　　ハードウェア構成でのイメージ なぜ、プッシュダウンスタック？ 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 研究テーマ 内部処理装置 記憶装置 入力記号列 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 難しいことはさておいて… (例を見てみましょう) 教科書p.68例3.1 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 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 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 δ：状態遷移関数 K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 ) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 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 ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 ) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 動作のトレース (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 ) 受理 拒否 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 状態遷移図 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 動作のトレース 自分で確認しよう 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) 受理 拒否 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 練習 教科書のp.71 問題3.1の DPDA の動作を いろいろな入力に対して調べてみよう。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 非決定性プッシュダウンオートマトン DPDAでの状態遷移関数部分が １対多の写像になる。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 DPDA M の定義（再） M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合　（#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K ) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 NPDA M の定義（再） M = <K, Σ, Γ, δ, q0, Z0, F> K:内部状態の集合　（#K < ∞） Σ：入力アルファベット （#Σ < ∞） Γ：プッシュダウンアルファベット（#Γ < ∞） δ：状態遷移関数 K×(Σ∪{ε})×Γ → ２K×Γ* q0：初期状態 (q0 ∈K ) Z0：ボトムマーカ ( Z0∈Γ) F：最終状態 ( F ⊂ K ) 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 DPDA M の例 M = <K, Σ, Γ, δ, q0, Z0, F> （教科書p.73の例3.2） 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 NPDA M の例 K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( 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 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 状態遷移図 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 今日の設問（１番だけ提出，５分） (q0, aaabbbcc, Z0) |*- ? aaabbbcc は受理されるか？ される場合は、その動作の様子を様相表現で示しなさい。 aabbbccc は受理されるか？ 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 ここまでのまとめ プッシュダウンスタック プッシュダウンオートマトン 決定性 非決定性 PDAはFAを含む（PDAはFAよりも文字列認識能力は高い。）　＜＝（Why?） DPDA は NPDA よりも能力は低い。 （証明はしませんが、事実です。） 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 次回は、チューリングマシンです。 チューリングマシンは、アルゴリズムや計算に関する理論の基礎を与えてくれます。 チューリングマシンと、認識可能な言語との対応（チョムスキー階層）の話しもやがて出てきます（第５章）。 計算量・計算の複雑さなどの話題にも触れましょう。　　お楽しみに！ 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 ここまで積み残してきているもの Myhill-Nerodeの定理 （DFAにおける）ポンピング補題　など （後日説明しますが、余裕のある人はポンピング定理をチャレンジ問題と思って、独学してみてください。） 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2017年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部 お知らせ 本講義は定期試験を行いません。 レポート課題が課されます。 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部