東京工科大学 コンピュータサイエンス学部 亀田弘之

Presentation on theme: "東京工科大学 コンピュータサイエンス学部 亀田弘之"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18 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は入力文字列 を受理 2017年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

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

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

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

23 ２．課題 次のε-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年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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