計算の理論 I ε-動作を含むNFA 火曜３校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科
今日の講義内容 ε-動作を含むNFA ε-CLOSURE(ε-閉包) ミニテスト 教科書 2.5節 p.80 正則表現とのつなぎ 次回の等価性の基礎 ミニテスト 平成16年5月25日 佐賀大学知能情報システム学科
ε-動作を含むNFA ε-動作を含むNFA Wがε-動作を含むNFAで受理 定義式 M (Q, Σ, δ, q0, F) → δ(q, a) ＝状態qからラベルaの遷移で移る先の状態の集合 平成16年5月25日 佐賀大学知能情報システム学科
ε-動作を含む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日 佐賀大学知能情報システム学科
ε-CLOSURE ある状態qからε-動作のみで移れる先の状態の集合 ε-CLOSUREの定義 文字列に対する遷移関数 を定義するため 文字列に対する遷移関数 を定義するため ε-CLOSUREの定義 ε-CLOSURE(q) ＝遷移図からラベルがεでない有向辺を取り去った上で、qから到達可能な頂点の集合 ε-CLOSURE(P) : Pは状態の集合 ＝ 平成16年5月25日 佐賀大学知能情報システム学科
ε-CLOSUREの例 ε-CLOSURE(q0)={q0, q1, q2} ε-CLOSURE(q1)={q1, q2} 1 開始 ラベルがεである暗黙的な辺 （長さ0の辺) 平成16年5月25日 佐賀大学知能情報システム学科
a ε a q q´ qからaの辺で直接到達できる状態の集合 qからaをラベルに持つ道（εを含む）を通って到達できる状態の集合 平成16年5月25日 佐賀大学知能情報システム学科
平成16年5月25日 佐賀大学知能情報システム学科
ε-動作ありNFAの受理言語 定義 平成16年5月25日 佐賀大学知能情報システム学科
受理の例 0: 01: 平成16年5月25日 佐賀大学知能情報システム学科
ε-動作を含むNFA 例１ ε-動作を含むNFA ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) δは下表 1 ε 1 ε q0 q0, q1 - q2 q1 平成16年5月25日 佐賀大学知能情報システム学科
例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日 佐賀大学知能情報システム学科
ε-動作を含むNFA 例2 ε-動作を含むNFA ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) δは下表 1 ε 1 ε q0 - q1 q0, q2 q2 平成16年5月25日 佐賀大学知能情報システム学科
例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日 佐賀大学知能情報システム学科
ミニテストと次回内容 ミニテスト ミニテストを提出すること 次回(6/1)内容 教科書・資料を見ても、友達と相談しても良い 15分後に指名された人は板書 ミニテストを提出すること 出したら帰って良し 次回(6/1)内容 ε-動作を含むNFAと等価なNFA 平成16年5月25日 佐賀大学知能情報システム学科