計算の理論 I －数学的概念と記法－

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

Download Report