計算の理論 I 正則表現とFAとの等価性 月曜3校時 大月 美佳 平成15年6月16日 佐賀大学知能情報システム学科.

Slides:



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

計算の理論 I 文脈自由文法 月曜3校時 大月 美佳 平成15年6月30日 佐賀大学知能情報システム学科.
コンパイラ 2011年10月17日
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
計算の理論 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日 佐賀大学理工学部知能情報システム学科.
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 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 -言語とオートマトン- 月曜3校時 大月 美佳.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 II 時間量と領域量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
計算の理論 II 計算量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 文脈自由文法の標準形 月曜3校時 大月美佳.
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳 平成15年6月2日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー正則表現とFAの等価性 その1ー
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析ー
計算の理論 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校時 大月 美佳.
計算の理論 I -講義について+αー 月曜3校時 大月美佳 平成31年5月18日 佐賀大学理工学部知能情報システム学科.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 反復補題 火曜3校時 大月 美佳 平成16年7月13日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
コンパイラ 2012年10月11日
形式言語とオートマトン2016 ー有限オートマトンー 第4日目
計算の理論 I ε-動作を含むNFAと等価なDFA
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
形式言語とオートマトン Formal Languages and Automata 第5日目
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
計算の理論 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 正則表現とFAとの等価性 月曜3校時 大月 美佳 平成15年6月16日 佐賀大学知能情報システム学科

今日の講義内容 正則表現補足 正則表現とFAの等価性 ミニテスト 正則表現→ε-NFA DFA(NFA)→正則表現 平成15年6月16日 佐賀大学知能情報システム学科

正規表現補足 慣れるためには、訓練が必要。 (00+1)*のバリエーション 記号の連続の制限 いろいろと当たってみる (000+1)* : 0の個数が3の倍数連続 (0000+1)* : 0の個数が4の倍数連続 記号の連続の制限 (1+01)*(ε+0) : 2個以上続く0を含まない いろいろと当たってみる 教科書3.1.4 p.98~99 平成15年6月16日 佐賀大学知能情報システム学科

今日の新しいこと 正則表現とFAの等価性 正則表現からのε-動作を含むNFAの作り方 DFAからの正則表現の作り方 →p.111~116 3.2.3項 (例3.8, p. 115) DFAからの正則表現の作り方 →p.100~111 3.2.1, 3.2.2項 (例3.5, p. 103, 例3.6, p.109) NFA 正則表現 ε-動作を含む DFA 平成15年6月16日 佐賀大学知能情報システム学科

正則表現からのε-動作を含むNFAの作り方 括弧つきに書き換える (00+1) → ((00)+1)* 分解していく r = r1* r1 = r2+r3, r3 =1 r2 = r4+r5, r4 =1 , r5 =1 * + 連接 1 平成15年6月16日 佐賀大学知能情報システム学科

NFAの作り方 (定理3.7 図3.16 p.113) 末端(最小構成)をFAに変換する r =ε r =φ r = a * + 連接 1 q0 開始 * q0 qf + 開始 連接 1 q0 a qf 開始 平成15年6月16日 佐賀大学知能情報システム学科

NFAの作り方 (定理3.7 図3.17 p.113) 末端から根に向かってどんどん変換する r =r1+r2 r =r1r2 → 図3.17 (b) r = r1* → 図3.17 (c) * + 連接 1 平成15年6月16日 佐賀大学知能情報システム学科

図3.17(a) r1 のNFA r2 のNFA 最終状態が1個だけ ε ε + ε ε q1 f1 開始 q1 f1 開始 q0 f0 平成15年6月16日 佐賀大学知能情報システム学科

図3.17(b) r1 のNFA r2 のNFA 最終状態が1個だけ 連接 q1 f1 開始 q1 f1 開始 q2 f2 開始 q2 f2 平成15年6月16日 佐賀大学知能情報システム学科

図3.17(c) r1 のNFA 最終状態が1個だけ * ε ε ε ε q1 f1 開始 q0 q1 f1 f0 開始 平成15年6月16日 佐賀大学知能情報システム学科

どんどんやってみる * やってみてね + 連接 1 1 ε ε 1 q5 q6 q8 q7 q1 q2 q3 q4 開始 q1 q2 開始 q3 q4 ε 開始 * やってみてね + q1 q2 開始 q3 q4 ε 連接 1 q5 q6 1 開始 q1 q2 開始 q3 q4 開始 平成15年6月16日 佐賀大学知能情報システム学科

NFAの生成例 正規表現 : 01*+1 括弧つきに書き換える 分解していく r r1 r2 r3 r4 r5 01*+1 → ((0(1*))+1) 分解していく r=r1+r2, r1=0(1*), r2=1 r1=r3r4, r3=0, r4=1* r4=r5*, r5=1 r + r1 r2 連接 1 r3 r4 * r5 1 平成15年6月16日 佐賀大学知能情報システム学科

NFAの生成例 (つづき 1) 正規表現 : 01*+1 最小構成をFAに変換する FAを組みあげていく r4=r5*, r5=1 連接 1 r3 r4 正規表現 : 01*+1 最小構成をFAに変換する FAを組みあげていく r4=r5*, r5=1 r1=r3r4 , r3=0 r=r1+r2 , r2=1 * r5 1 q5 1 q6 開始 q3 q4 開始 q1 1 q2 開始 平成15年6月16日 佐賀大学知能情報システム学科

NFAの生成例 (つづき 2) 4.1. r4=r5* r5=1 ε ε 1 ε ε r r1 r2 r3 r4 r5 q7 q5 q6 + r1 r2 4.1. r4=r5* 連接 1 r3 r4 * r5 ε 1 q7 ε q5 1 q6 ε q8 r5=1 ε 平成15年6月16日 佐賀大学知能情報システム学科

NFAの生成例 (つづき 3) 4.2. r1=r3r4 r3=0 r5=1 r4=r5* ε 1 r r1 r2 r4 r5 r3 q6 + 連接 1 * r r1 r2 r4 r5 r3 4.2. r1=r3r4 q6 q3 q4 開始 q5 1 r3=0 r5=1 q7 ε q8 r4=r5* 平成15年6月16日 佐賀大学知能情報システム学科

NFAの生成例 (つづき 4) r2=1 4.3. r=r1+r2 r4=r5* r5=1 1 ε r r1 r2 r4 r5 r3 q1 連接 1 * r r1 r2 r4 r5 r3 NFAの生成例 (つづき 4) r2=1 4.3. r=r1+r2 q1 q2 1 q6 q3 q4 開始 q5 r5=1 q7 ε q8 r4=r5* q10 q9 平成15年6月16日 佐賀大学知能情報システム学科

DFA→正則表現 (3.2.1項 p.100~) 考え方 ある状態からある状態の間の状態を0からひとつずつ増やしていって、 状態の任意の組からなる道が生成することのできる文字列の正則表現を再帰的に拡張していき、 最後に、初期状態から最終状態への道が生成できる文字列の正則表現を求める。 平成15年6月16日 佐賀大学知能情報システム学科

数学的に定義 Mの状態をqiから途中qjより大きな番号の状態を通らずに、qjにたどり着くことのできる入力列の集合 平成15年6月16日 佐賀大学知能情報システム学科

正則表現の式との対応 ↓ 平成15年6月16日 佐賀大学知能情報システム学科

正則表現の生成例その1 q1 q2 開始 q3 1 0,1 δ 1 q1 q2 q3 平成15年6月16日 佐賀大学知能情報システム学科

どんどん進める k=1 q1 q2 開始 q3 1 0,1 平成15年6月16日 佐賀大学知能情報システム学科

どんどん進める k=2 q1 q2 開始 q3 1 0,1 平成15年6月16日 佐賀大学知能情報システム学科

最終状態への道 k=3 q1 q2 開始 q3 1 0,1 平成15年6月16日 佐賀大学知能情報システム学科

まとめ方が難しい? 以下のルールを活用せよ 平成15年6月16日 佐賀大学知能情報システム学科

正則表現の生成例その2 下の状態図に対応する正則表現を求めよ。 A 開始 C 1 B 平成15年6月16日 佐賀大学知能情報システム学科

とりあえず番号をつける 1から! A → 1 B → 2 C → 3 A A C B A B A C B A B B C C A C B C C 1 B A B 開始 A C 1から! B A A → 1 B → 2 C → 3 B B C C A C B C 平成15年6月16日 佐賀大学知能情報システム学科

状態Aが加わった k=1 その1 ε ε A A ε ε A B ε A B A ε ε A A B ε 平成15年6月16日 佐賀大学知能情報システム学科

状態Aが加わった k=1 その2 ε ε A C A C ε ε B A ε B A A ε ε B A A ε 平成15年6月16日 佐賀大学知能情報システム学科

状態Aが加わった k=1 その3 ε ε B A B A ε ε ε B A C ε B C A ε ε B A A C ε 平成15年6月16日 佐賀大学知能情報システム学科

状態Aが加わった k=1 その4 ε ε C A C A ε ε ε B A C ε B C A ε ε B A A C ε 平成15年6月16日 佐賀大学知能情報システム学科

状態Aが加わった k=1 その5 ε ε C A C A ε 平成15年6月16日 佐賀大学知能情報システム学科

さらに状態Bが加わった k=2 例1 ε A ε ε A ε ε B A A B ε ε A B ε B A ε ε ε 平成15年6月16日 佐賀大学知能情報システム学科

どんどん進める k=2 平成15年6月16日 佐賀大学知能情報システム学科

最終状態への道 k=3 平成15年6月16日 佐賀大学知能情報システム学科

最終解 k=3 平成15年6月16日 佐賀大学知能情報システム学科

状態消去法 (3.2.2項 p.105~) 状態を正則表現に順次置き換えていく オートマトンの全ての辺のラベルを正則表現に書き改める 受理状態qと開始状態q0のみを残して、後は消去する(消去法: p.106-107, 図3.7→図3.8) q≠q0の場合には、この2状態オートマトンに図3.9(p. 108)のようなラベル付けをする q=q0の場合には、この1状態オートマトンに図3.10(p. 109)のようなラベル付けをする 3と4の和から全体を求める 平成15年6月16日 佐賀大学知能情報システム学科

消去後のFAと正則表現 q0 q q0 図3.9 p.108 →(R+SU*T)*SU* 図3.10 p.109 →R* S T R U 開始 q S R T U →(R+SU*T)*SU* 図3.10 p.109 q0 →R* 開始 R 平成15年6月16日 佐賀大学知能情報システム学科

状態消去法の例 (例3.6 p.109) 末尾から2文字目か3文字目に1がある列の全体を受理するFA A B C D 1 0,1 0,1 開始 平成15年6月16日 佐賀大学知能情報システム学科

ラベルの書き換え 正則表現に書き換える A B C D 1 0+1 0+1 0+1 開始 平成15年6月16日 佐賀大学知能情報システム学科

状態Bの消去 繰り返し作業を省くためこの時点で消去 A B C C D A 1 0+1 φ+1φ*(0+1) =1(0+1) φ φ 0+1 開始 平成15年6月16日 佐賀大学知能情報システム学科

状態Cの消去 (A, D)の組用 A C D A D 1(0+1) 0+1 φ+1(0+1)φ*(0+1) =1(0+1)(0+1) φ φ 1(0+1)(1+0) D 開始 0+1 ((0+1)+1(0+1)(1+0)φ*φ)*(1(0+1)(0+1))φ* =(0+1)*1(0+1)(1+0) 平成15年6月16日 佐賀大学知能情報システム学科

状態Dの消去 (A, C)の組用 C D A C 0+1 後続状態がない! 1(0+1) 開始 0+1 ((0+1)+1(0+1)φ*φ)*(1(0+1))φ* =(0+1)*1(0+1) 平成15年6月16日 佐賀大学知能情報システム学科

最終的な正則表現 (A, C)と(A, D)の正則表現の和 → (0+1)*1(0+1)+(0+1)*1(0+1)(0+1) 平成15年6月16日 佐賀大学知能情報システム学科

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