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

Slides:



Advertisements
Similar presentations
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
Advertisements

データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
形式言語とオートマトン2011 ー有限オートマトンー 第3日目
データ構造と アルゴリズム 知能情報学部 新田直也.
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
スタック長の 特徴付けによる 言語の非DCFL性 証明
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
第2章 「有限オートマトン」.
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン2008 ー有限オートマトンー
東京工科大学 コンピュータサイエンス学部 担当 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2012 ー有限オートマトンー 第3日目
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー 正則表現(今度こそ) ー 月曜3校時 大月 美佳.
形式言語とオートマトン Formal Languages and Automata 第4日目
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2017 ー有限オートマトンー 第3日目
言語プロセッサ ー第9回目ー 構文解析(続き).
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳 平成15年6月2日 佐賀大学知能情報システム学科.
計算の理論 I 正則表現とFAとの等価性 月曜3校時 大月 美佳 平成15年6月16日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー正則表現とFAの等価性 その1ー
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 非決定性有限オートマトン(NFA)
5.チューリングマシンと計算.
計算の理論 I -プッシュダウンオートマトン-
計算の理論 I ー正則表現とFAの等価性ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2016 ー有限オートマトンー 第4日目
計算の理論 I ε-動作を含むNFAと等価なDFA
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
形式言語とオートマトン Formal Languages and Automata 第5日目
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
Presentation transcript:

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

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

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

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

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

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

確認問題 下図のε-NFAをDFAに書き換えなさい。 a 4 b b ε ε ε a 1 2 3 6 7 8 b 5 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)という用語は、本を読んでいると時々出てきます。 オートマトンの動作状況を表現する単なる 1つの方法にすぎません。 でも、便利ですよね。

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

Let’s get down to today’s topics. ここから新しい話し Let’s get down to today’s topics. (第3章に入ります)

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

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

プッシュダウンスタックのイメージ 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) |- (q1, ε, AZ0) 受理 拒否

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

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

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×(Σ∪{ε})×Γ → 2K×Γ* 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

状態遷移図

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

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

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

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