計算の理論 I ε-動作を含むNFA 月曜３校時大月美佳平成15年5月26日佐賀大学知能情報システム学科 1 今日の講義内容 1. ε-動作を含むNFA 教科書 2.5節 p.80 正則表現とのつなぎ 2. ε-CLOSURE(ε-閉包) 教科書2.5.3項 p.82 次回の等価性の基礎 3. ミニテスト平成15年5月26日佐賀大学知能情報システム学科 2 ε-動作を含むNFA  ε-動作を含むNFA ＝空入力εによる状態遷移が許されたNFA  Wがε-動作を含むNFAで受理＝初期状態から最終状態へ至る道がw ただし、wに明示的にεは含まれない  定義式 M (Q, Σ, δ, q0, F) δ＝Q×(Σ∪{ε})からQのベキ集合への関数 → δ(q, a) ＝状態qからラベルaの遷移で移る先の状態の集合平成15年5月26日佐賀大学知能情報システム学科 3 ε-動作を含むNFAの例受理入力列の例 Σ∪{ε} δ 1. 002→00εε2 0 1 2 ε 2. 012 →0ε1ε2 q0 {q0 } ○ ○ 3. 12 →ε1ε2 {q １} q1 ○ {q１ } ○ 4. 2 →εε2 {q ２} q2 ○ ○ {q2 } ○ 0 開始平成15年5月26日 q0 1 ε q1 佐賀大学知能情報システム学科 2 ε q2 4 ε-CLOSURE  ある状態qからε-動作のみで移れる先の状態の集合文字列に対する遷移関数 ˆ を定義するため  ε-CLOSUREの定義 – ε-CLOSURE(q) ＝遷移図からラベルがεでない有向辺を取り去った上で、qから到達可能な頂点の集合 – ε-CLOSURE(P) : Pは状態の集合＝   CLOSURE(q) 平成15年5月26日 qP 佐賀大学知能情報システム学科 5 ε-CLOSUREの例  ε-CLOSURE(q0)={q0, q1, q2}  ε-CLOSURE(q1)={q1, q2}  ε-CLOSURE(q2)={q2} 0 開始 q0 ε 1 ε q1 2 ε q2 ε ε ラベルがεである暗黙的な辺（長さ0の辺) 平成15年5月26日佐賀大学知能情報システム学科 6 ˆの定義 1) ˆ (q,  )    CLOSURE(q) 2) ˆ (q, wa )    CLOSURE( P) ˆ(q, a) a q ε q´ a  ( q, a ) ただし、 w   *, q  , P  { p | ある ˆ (q, w)の元 rに対して p   (r , a)} ˆ (q, a)は必ずしも  (q, a)と等しくない。 qからaの辺で直接到達できる状態の集合 qからaをラベルに持つ道（εを含む）を通って到達できる状態の集合平成15年5月26日佐賀大学知能情報システム学科 7 と ˆの拡張 1) ˆ (q,  )    CLOSURE(q ) 2) ˆ (q, wa )    CLOSURE( P) ただし、 w   *, q  , P  { p | ある ˆ (q, w)の元 rに対して r   (r , a )} さらに、状態の集合 R( Q)に対して 3)  (R , a)    (q, a) qR 4) ˆ (R , w)   ˆ (q, w) 平成15年5月26日 qR 佐賀大学知能情報システム学科 8 ε-動作ありNFAの受理言語  定義 M  (Q, ,  , q0 , F )が受理する言語は {w | ˆ (q , w)はFの元を含む } 0 であり L( M )と書く。平成15年5月26日佐賀大学知能情報システム学科 9 受理の例 1. 0: ˆ (q0 ,0)    CLOSURE( (ˆ (q0 ,  ),0))    CLOSURE( ({q0 , q1 , q2 },0))    CLOSURE( (q0 ,0)   (q1 ,0)   (q2 ,0))    CLOSURE({q0 } ○○)    CLOSURE({q0 })  {q0 , q1 , q2 } ˆ (q0 ,01)    CLOSURE( (ˆ (q0 ,0),1))    CLOSURE( ({q0 , q1 , q2 },1))    CLOSURE( (q0 ,1)   (q1 ,1)   (q2 ,1))    CLOSURE(○{q1} ○)   佐賀大学知能情報システム学科  CLOSURE({q1})  {q1 , q2 } 平成15年5月26日 2. 01: 10 ε-動作を含むNFA 例１  ε-動作を含むNFA ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) δは下表 q0 q1 q2 平成15年5月26日 0 1 ε q0, q1 q2 q2 q 0, q1 q0, q1 q1 佐賀大学知能情報システム学科 11 例1 ε-CLOSURE ε 開始 q1 q0 ε ε 0 1 ε q0 q0, q1 - q2 q1 q2 q0, q1 - q2 q0, q1 - q1 平成15年5月26日 ε q2 ε ε-CLOSURE ε q0 q0, q1, q2 q1 q1 q2 q1, q2 佐賀大学知能情報システム学科 12 ε-動作を含むNFA 例2  ε-動作を含むNFA ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) δは下表 q0 q1 q2 平成15年5月26日 0 q0 q1 1 q 0, q2 q2 佐賀大学知能情報システム学科 ε q1 q0 q0 13 例2 ε-CLOSURE ε ε 開始 q0 ε 0 1 ε q0 q0 - q1 q1 - q2 q1 q0, q2 q0 q2 平成15年5月26日 q0 ε q1 ε q2 ε ε-CLOSURE ε q0 q0, q1 q1 q0, q1 q2 q0, q1, q2 佐賀大学知能情報システム学科 14 ミニテストと次回内容  ミニテスト教科書・資料を見ても、友達と相談しても良い 15分後に指名された人は板書  ミニテストを提出すること出したら帰って良し  次回(6/2)内容 ε-動作を含むNFAと等価なDFA 平成15年5月26日佐賀大学知能情報システム学科 15