計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳 平成15年6月2日 佐賀大学知能情報システム学科.

Slides:



Advertisements
Similar presentations
計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
Advertisements

正規表現からのDFA直接構成.
計算の理論 I 文脈自由文法 月曜3校時 大月 美佳 平成15年6月30日 佐賀大学知能情報システム学科.
コンパイラ 2011年10月17日
計算の理論 II 帰納的関数(つづき) 月曜4校時 大月美佳.
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
計算の理論 II NP完全 月曜4校時 大月美佳.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
コンパイラ 2012年10月15日
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン Formal Languages and Automata 第4日目
形式言語とオートマトン2008 ー有限オートマトンー
計算の理論 II NP完全 月曜5校時 大月美佳 平成17年1月17日 佐賀大学理工学部知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 II 帰納的関数 月曜4校時 大月美佳.
計算の理論 II 帰納的関数2 月曜4校時 大月美佳.
計算の理論 I 正則表現 火曜3校時 大月 美佳 平成16年6月8日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現(今度こそ) ー 月曜3校時 大月 美佳.
計算の理論 I 正則表現 月曜3校時 大月 美佳 平成15年6月9日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
形式言語とオートマトン Formal Languages and Automata 第4日目
計算の理論 II Turing機械 月曜4校時 大月美佳.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 II 言語とクラス 月曜4校時 大月美佳.
計算の理論 II 時間量と領域量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
計算の理論 II 計算量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 文脈自由文法の標準形 月曜3校時 大月美佳.
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
計算の理論 I 正則表現とFAとの等価性 月曜3校時 大月 美佳 平成15年6月16日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー正則表現とFAの等価性 その1ー
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
計算の理論 I 反復補題 月曜3校時 大月 美佳 平成15年7月14日 佐賀大学知能情報システム学科.
計算の理論 I 非決定性有限オートマトン(NFA)
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
計算の理論 I -プッシュダウンオートマトン-
計算の理論 I ー正則表現とFAの等価性ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
ミニテスト12解答 月曜3校時 大月 美佳.
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
計算の理論 I -講義について+αー 月曜3校時 大月美佳 平成31年5月18日 佐賀大学理工学部知能情報システム学科.
計算の理論 I 文脈自由文法 月曜3校時 大月美佳.
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 反復補題 火曜3校時 大月 美佳 平成16年7月13日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
形式言語とオートマトン2016 ー有限オートマトンー 第4日目
計算の理論 I ε-動作を含むNFAと等価なDFA
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
形式言語とオートマトン Formal Languages and Automata 第5日目
計算の理論 I -講義について+αー 火曜3校時 大月美佳 平成31年8月23日 佐賀大学理工学部知能情報システム学科.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
計算の理論 II 時間量と領域量 月曜4校時 大月美佳 2019/9/13 佐賀大学理工学部知能情報システム学科.
計算の理論 I 最小化 月曜3校時 大月 美佳 平成15年6月23日 佐賀大学知能情報システム学科.
Presentation transcript:

計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳 平成15年6月2日 佐賀大学知能情報システム学科

今日の講義内容 ε-動作を含むNFA遷移関数と受理 ε-動作ありNFA→ε-動作なしNFA ε-動作なしNFA→DFA ミニテスト 復習・補足 ε-動作ありNFA→ε-動作なしNFA ε-動作なしNFA→DFA ミニテスト 平成15年6月2日 佐賀大学知能情報システム学科

a ε a q q´ qからaの辺で直接到達できる状態の集合 qからaをラベルに持つ道(εを含む)を通って到達できる状態の集合 平成15年6月2日 佐賀大学知能情報システム学科

平成15年6月2日 佐賀大学知能情報システム学科

ε-動作ありNFAの受理言語 定義 平成15年6月2日 佐賀大学知能情報システム学科

受理の例 0: 01: 平成15年6月2日 佐賀大学知能情報システム学科

ε-動作なしNFAと ε-動作ありNFAの等価性 ε-動作ありNFA: M (Q, Σ, δ, q0, F)が ε-動作なしNFA: M´(Q, Σ, δ´, q0, F´) で模倣できる(帰納法)。 平成15年6月2日 佐賀大学知能情報システム学科

ε-動作ありNFAを模倣する ε-動作なしNFAの例 δ δ´ 1 2 ε q0 {q0 } φ {q1 } q1 {q2 } q2 {q2 } 1 2 q0 {q0, q1, q2 } {q1, q2 } {q2 } q1 φ q2 q2 q1 2 q0 ε 1 1 2 0,1 1,2 q0 q1 q2 0,1,2 開始 開始 平成15年6月2日 佐賀大学知能情報システム学科

ε-遷移無しNFAからDFAへ サブセット構成法 1 2 0, 1, 2 1 2 0,1 1 2 1 2 *→[q0 ] 1 2 *→[q0 ] [q0, q1, q2 ] [q1, q2 ] [q2] *[q0, q1, q2 ] [q1, q2] *[q1, q2 ] [φ] *[q2] 1 2 *→q0 {q0, q1, q2 } {q1, q2 } {q2 } q1 φ *q2 1 2 0, 1, 2 1 2 0,1 [q0 ] [q0 , q1 , q2] [q1 , q2] [q0 ] [φ] 1 2 開始 平成15年6月2日 佐賀大学知能情報システム学科

ε-動作を含むNFA 例1 ε-動作を含むNFA ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) δは下表 1 ε 1 ε q0 q0, q1 - q2 q1 平成15年6月2日 佐賀大学知能情報システム学科

例1 ε-CLOSURE q ECLOSE(q) q0 q0, q1, q2 q1 q2 q1, q2 ε ε ε ε ε q0 q1 q2 開始 ε ε ε q ECLOSE(q) q0 q0, q1, q2 q1 q2 q1, q2 1 ε q0 q0, q1 - q2 q1 平成15年6月2日 佐賀大学知能情報システム学科

例1 NFA δ´(q0, 0)=EClOSE(δ(ECLOSE(q0 ), 0)) = EClOSE(δ({q0, q1, q2}, 0)) = EClOSE({q0, q1, q2})= {q0, q1, q2} δ´(q0, 1)=EClOSE(δ(ECLOSE(q0 ), 1)) = EClOSE(δ({q0, q1, q2}, 1)) = EClOSE({q0, q1})= {q0, q1, q2} δ´(q1, 0)=EClOSE(δ(ECLOSE(q1 ), 0)) = EClOSE(δ({q1}, 0)) =EClOSE({q2})={q1, q2} δ´(q1, 1)=EClOSE(δ(ECLOSE(q1 ), 1)) = EClOSE(δ({q1}, 1)) = EClOSE(δ({q0, q1}, 1))={q0, q1, q2} δ´(q2, 0)=EClOSE(δ(ECLOSE(q2 ), 0)) = EClOSE(δ({q1, q2}, 0)) = EClOSE({q0, q1, q2}) = {q0, q1, q2} δ´(q2, 1)=EClOSE(δ(ECLOSE(q2 ), 1)) = EClOSE(δ({q1, q2}, 1)) = EClOSE({q0, q1}) = {q0, q1, q2} 1 *→q0 {q0, q1, q2} q1 {q1, q2} *q2 平成15年6月2日 佐賀大学知能情報システム学科

例1 NFA→DFA サブセット構成法 1 *→q0 {q0, q1, q2} q1 {q1, q2} *q2 1 *→[q0 ] 1 *→q0 {q0, q1, q2} q1 {q1, q2} *q2 1 *→[q0 ] [q0, q1, q2] *[q0, q1, q2] 平成15年6月2日 佐賀大学知能情報システム学科

ε-動作を含むNFA→NFA 例2 ε-動作を含むNFA ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) δは下表 1 ε q0 - q1 q0, q2 q2 平成15年6月2日 佐賀大学知能情報システム学科

例2 ε-CLOSURE q ECLOSE q0 q0, q1 q1 q2 q0, q1, q2 ε ε ε ε ε ε q0 q1 q2 開始 ε ε ε ε 1 ε q0 - q1 q0, q2 q2 q ECLOSE q0 q0, q1 q1 q2 q0, q1, q2 平成15年6月2日 佐賀大学知能情報システム学科

例2 NFA δ´(q0, 0)=EClOSE(δ(EClOSE( q0 ), 0))= 1 →q0 q1 *q2 平成15年6月2日 佐賀大学知能情報システム学科

例2 NFA→DFA サブセット構成法 1 →q0 q1 *q2 1 →[q0 ] 平成15年6月2日 佐賀大学知能情報システム学科

ミニテストと次回内容 ミニテスト ミニテストを提出すること 次回(6/9)内容 教科書・資料を見ても、友達と相談しても良い 15分後に指名された人は板書 ミニテストを提出すること 出したら帰って良し 次回(6/9)内容 正則(正規)表現 平成15年6月2日 佐賀大学知能情報システム学科