計算の理論 I ε-動作を含むNFAと等価なDFA

Presentation on theme: "計算の理論 I ε-動作を含むNFAと等価なDFA"— Presentation transcript:

1 計算の理論 I ε-動作を含むNFAと等価なDFA
月曜３校時 大月 美佳 平成16年6月1日 佐賀大学知能情報システム学科

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

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

4 平成16年6月1日 佐賀大学知能情報システム学科

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

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

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

8 ε-動作ありNFAを模倣する ε-動作なしNFAの例
δ δ´ 1 2 ε q0 {q0 } φ {q１ } q1 {q２ } 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 開始 開始 平成16年6月1日 佐賀大学知能情報システム学科

9 ε-遷移無し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 開始 平成16年6月1日 佐賀大学知能情報システム学科

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

11 例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 平成16年6月1日 佐賀大学知能情報システム学科

12 例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} δ´(q１, 0)=ECLOSE(δ(ECLOSE(q1 ), 0)) = ECLOSE(δ({q1}, 0)) =ECLOSE({q2})={q1, q2} δ´(q１, 1)=ECLOSE(δ(ECLOSE(q1 ), 1)) = ECLOSE(δ({q1}, 1)) = ECLOSE({q0, q1}) = {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)) 1 *→q0 {q0, q1, q2} q1 {q1, q2} *q2 平成16年6月1日 佐賀大学知能情報システム学科

13 例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] 平成16年6月1日 佐賀大学知能情報システム学科

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

15 例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 平成16年6月1日 佐賀大学知能情報システム学科

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

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

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