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

Presentation on theme: "計算の理論 I ε-動作を含むNFA 火曜３校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科."— Presentation transcript:

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

2 今日の講義内容 ε-動作を含むNFA ε-CLOSURE(ε-閉包) ミニテスト 教科書 2.5節 p.80 正則表現とのつなぎ
次回の等価性の基礎 ミニテスト 平成16年5月25日 佐賀大学知能情報システム学科

3 ε-動作を含むNFA ε-動作を含むNFA Wがε-動作を含むNFAで受理 定義式 M (Q, Σ, δ, q0, F)
→ δ(q, a) ＝状態qからラベルaの遷移で移る先の状態の集合 平成16年5月25日 佐賀大学知能情報システム学科

4 ε-動作を含むNFAの例 受理入力列の例 δ Σ∪{ε} 002→00εε2 012 →0ε1ε2 12 →ε1ε2 2 →εε2 2 ε
1 2 ε q0 {q0 } ○ {q１ } q1 {q２ } q2 {q2 } q2 q1 2 q0 ε 1 開始 平成16年5月25日 佐賀大学知能情報システム学科

5 ε-CLOSURE ある状態qからε-動作のみで移れる先の状態の集合 ε-CLOSUREの定義 文字列に対する遷移関数 を定義するため
文字列に対する遷移関数 を定義するため ε-CLOSUREの定義 ε-CLOSURE(q) ＝遷移図からラベルがεでない有向辺を取り去った上で、qから到達可能な頂点の集合 ε-CLOSURE(P) : Pは状態の集合 ＝ 平成16年5月25日 佐賀大学知能情報システム学科

6 ε-CLOSUREの例 ε-CLOSURE(q0)={q0, q1, q2} ε-CLOSURE(q1)={q1, q2}
1 開始 ラベルがεである暗黙的な辺 （長さ0の辺) 平成16年5月25日 佐賀大学知能情報システム学科

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

8 平成16年5月25日 佐賀大学知能情報システム学科

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

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

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

12 例1 ε-CLOSURE ε-CLOSURE q0 q0, q1, q2 q1 q2 q1, q2 ε ε ε ε ε q0 q1 q2
開始 ε ε ε 1 ε q0 q0, q1 - q2 q1 ε-CLOSURE q0 q0, q1, q2 q1 q2 q1, q2 平成16年5月25日 佐賀大学知能情報システム学科

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

14 例2 ε-CLOSURE ε-CLOSURE q0 q0, q1 q1 q2 q0, q1, q2 ε ε ε ε ε ε q0 q1 q2
開始 ε ε ε ε 1 ε q0 - q1 q0, q2 q2 ε-CLOSURE q0 q0, q1 q1 q2 q0, q1, q2 平成16年5月25日 佐賀大学知能情報システム学科

15 ミニテストと次回内容 ミニテスト ミニテストを提出すること 次回(6/1)内容 教科書・資料を見ても、友達と相談しても良い
15分後に指名された人は板書 ミニテストを提出すること 出したら帰って良し 次回(6/1)内容 ε-動作を含むNFAと等価なNFA 平成16年5月25日 佐賀大学知能情報システム学科