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

計算の理論 I
ε-動作を含むNFAと等価なDFA
月曜３校時
大月美佳
平成16年6月1日
佐賀大学知能情報システム学科
1
今日の講義内容
1. ε-動作を含むNFA遷移関数と受理
復習・補足
2. ε-動作ありNFA→ε-動作なしNFA
3. ε-動作なしNFA→DFA
4. ミニテスト
平成16年6月1日
佐賀大学知能情報システム学科
2
ˆの定義
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年6月1日
佐賀大学知能情報システム学科
3
と ˆの拡張
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)
平成16年6月1日
qR
佐賀大学知能情報システム学科
4
ε-動作ありNFAの受理言語
 定義
M  (Q, ,  , q0 , F )が受理する言語は
{w | ˆ (q , w)はFの元を含む }
0
であり L( M )と書く。
平成16年6月1日
佐賀大学知能情報システム学科
5
受理の例
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年6月1日
佐賀大学知能情報システム学科
6
ε-動作なしNFAと
ε-動作ありNFAの等価性
ε-動作ありNFA: M (Q, Σ, δ, q0, F)が
ε-動作なしNFA: M´(Q, Σ, δ´, q0, F´)
で模倣できる（帰納法）。
 - CLOSURE(q0 )が Fの元を含むとき
 F  {q0 }
F  
そうでないとき
F
 (q, a)  ˆ(q, a) (q  Q, a  )
平成16年6月1日
佐賀大学知能情報システム学科
7
ε-動作ありNFAを模倣する
ε-動作なしNFAの例
δ
δ´
0
1
2
ε
q0
{q0 }
φ
φ
{q１ }
q1
φ
{q１ }
φ
q2
φ
φ
{q2 }
0
q0
ε
1
q1
ε
0
1
2
q0
{q0, q1, q2 }
{q1, q2 }
{q2 }
{q２ }
q1
φ
{q1, q2 }
{q2 }
φ
q2
φ
φ
{q2 }
2
0
q2
q0
0,1
1
q1
1,2
2
q2
0,1,2
開始
平成16年6月1日
開始
佐賀大学知能情報システム学科
8
ε-遷移無しNFAからDFAへ
サブセット構成法
0
1
2
0
1
2
*→[q0 ]
[q0, q1, q2 ]
[q1, q2 ]
[q2]
*→q0
{q0, q1, q2 }
{q1, q2 }
{q2 }
*[q0, q1, q2 ]
[q0, q1, q2 ]
[q1, q2]
[q2]
q1
φ
{q1, q2 }
{q2 }
*[q1, q2 ]
[φ]
[q1, q2]
[q2]
*[q2]
[φ]
[φ]
[q2]
[φ]
[φ]
[φ]
[φ]
*q2
φ
φ
{q2 }
0
[q0 ]
0
[q0 , q1 , q2]
1
1
[q1 , q2]
2
2
0,1
[q0 ]
1
[φ]
0
2
開始
平成16年6月1日
0, 1, 2
佐賀大学知能情報システム学科
9
ε-動作を含むNFA 例１
 ε-動作を含むNFA
({q0, q1, q2}, {0, 1}, δ, q0, {q2})
δは下表
q0
q1
q2
平成16年6月1日
0
1
ε
q0, q1 q2
q2 q 0, q1 q0, q1 q1
佐賀大学知能情報システム学科
10
例1 ε-CLOSURE
ε
開始
q1
q0
ε
q2
ε
0
1
ε
q0
q0, q1
-
q2
q1
q2
q0, q1
-
q2
q0, q1
-
q1
平成16年6月1日
ε
q
q0
q1
q2
ε
ECLOSE(q)
q0, q1 , q2
q1
q1, q 2
佐賀大学知能情報システム学科
11
例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))
= ECLOSE({q0, q1}) = {q0, q1, q2}
平成16年6月1日
0
1
*→q0
{q0, q1, q2}
{q0, q1, q2}
q1
{q1, q2}
{q0, q1, q2}
*q2
{q0, q1, q2}
{q0, q1, q2}
佐賀大学知能情報システム学科
12
例1 NFA→DFA
サブセット構成法
0
1
*→q0
{q0, q1, q2}
{q0, q1, q2}
q1
{q1, q2}
{q0, q1, q2}
*q2
{q0, q1, q2}
{q0, q1, q2}
平成16年6月1日
0
1
*→[q0 ]
[q0, q1, q2]
[q0, q1, q2]
*[q0, q1, q2]
[q0, q1, q2]
[q0, q1, q2]
佐賀大学知能情報システム学科
13
ε-動作を含むNFA→NFA
例2
 ε-動作を含むNFA
({q0, q1, q2}, {0, 1}, δ, q0, {q2})
δは下表
q0
q1
q2
平成16年6月1日
0
q0
q1
1
q 0, q2
q2
佐賀大学知能情報システム学科
ε
q1
q0
q0
14
例2 ε-CLOSURE
ε
ε
開始
q0
ε
0
1
ε
q0 q0
-
q1
q1
-
q2 q1
q0, q2 q0
q2
平成16年6月1日
q0
ε
q1
q2
ε
q
q0
q1
q2
ε
ECLOSE
q0, q 1
q0, q 1
q0, q1 , q2
佐賀大学知能情報システム学科
15
例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))
=ECLOSE({q0})={q0, q1}
δ´(q1, 1)=EClOSE(δ(EClOSE( q1 ), 1)) =ECLOSE(δ({q0, q1}, 1))
=ECLOSE({q0, q2})={q0, q1, q2}
δ´(q2, 0)=EClOSE(δ(EClOSE( q2 ), 0)) =ECLOSE(δ({q0, q1, q2}, 0))
=ECLOSE({q0, q1})={q0, q1}
δ´(q2, 1)=EClOSE(δ(EClOSE( q2 ), 1))
0
1
=ECLOSE(δ({q0, q1, q2}, 1))
=ECLOSE({q0, q2})={q0, q1, q2} →q0 {q0, q1} {q0, q1, q2}
平成16年6月1日
q1
{q0, q1}
{q0, q1, q2}
*q2
{q0, q1}
{q0, q1, q2}
佐賀大学知能情報システム学科
16
例2 NFA→DFA
サブセット構成法
0
1
→q0
{q0, q1}
{q0, q1, q2}
q1
{q0, q1}
*q2
{q0, q1}
平成16年6月1日
0
1
→[q0 ]
[q0, q1]
[q0, q1, q2]
{q0, q1, q2}
[q0, q1]
[q0, q1]
[q0, q1, q2]
{q0, q1, q2}
[q0, q1, q2]
[q0, q1]
[q0, q1, q2]
佐賀大学知能情報システム学科
17
ミニテストと次回内容
 ミニテスト
教科書・資料を見ても、友達と相談しても良い
15分後に指名された人は板書
 ミニテストを提出すること
出したら帰って良し
 次回(6/8)内容
正則（正規）表現
平成16年6月1日
佐賀大学知能情報システム学科
18

Download Report