計算の理論 I
正則表現とFAとの等価性
月曜３校時
大月 美佳
平成15年6月16日
佐賀大学知能情報システム学科
1
今日の講義内容
1. 正則表現補足
2. 正則表現とFAの等価性
1. 正則表現→ε-NFA
2. DFA(NFA)→正則表現
3. ミニテスト
平成15年6月16日
佐賀大学知能情報システム学科
2
正規表現補足
慣れるためには、訓練が必要。
1. (00+1)*のバリエーション
(000+1)* : 0の個数が3の倍数連続
(0000+1)* : 0の個数が4の倍数連続
2. 記号の連続の制限
(1+01)*(ε+0) : 2個以上続く0を含まない
3. いろいろと当たってみる
教科書3.1.4 p.98～99
平成15年6月16日
佐賀大学知能情報システム学科
3
今日の新しいこと
1. 正則表現とFAの等価性
NFA
ε-動作を含む
NFA
DFA
正則表現
1.
正則表現からのε-動作を含むNFAの作り方
→p.111～116 3.2.3項 (例3.8, p. 115)
2.
DFAからの正則表現の作り方
→p.100～111 3.2.1, 3.2.2項 (例3.5, p. 103, 例3.6, p.109)
平成15年6月16日
佐賀大学知能情報システム学科
4
正則表現からのε-動作を含む
NFAの作り方
1. 括弧つきに書き換える
(00+1) → ((00)+1)*
2. 分解していく
1.
2.
3.
*
r = r 1*
r1 = r2+r3, r3 =1
r2 = r4+r5, r4 =1 , r5 =1
+
連接
0
平成15年6月16日
佐賀大学知能情報システム学科
1
0
5
NFAの作り方
(定理3.7 図3.16 p.113)
3. 末端（最小構成)をFAに変換する
1. r =ε
開始
q0
*
2. r =φ
開始
q0
+
qf
3. r = a
開始
平成15年6月16日
連接
q0
a
qf
佐賀大学知能情報システム学科
0
1
0
6
NFAの作り方
(定理3.7 図3.17 p.113)
3. 末端から根に向かってどんどん変換す
る
1. r =r1+r2
*
→ 図3.17 (a)
2. r =r1r2
+
→ 図3.17 (b)
3. r = r1*
連接
→ 図3.17 (c)
平成15年6月16日
佐賀大学知能情報システム学科
0
1
0
7
図3.17(a)
最終状態が1個だけ
r1 のNFA
開始
q1
f1
開始
q1
f1
ε
r2 のNFA
開始
q2
平成15年6月16日
+
ε
q0
f0
ε
f2
佐賀大学知能情報システム学科
ε
q2
f2
8
図3.17(b)
最終状態が1個だけ
r1 のNFA
開始
q1
f1
r2 のNFA
開始
q2
平成15年6月16日
開始
q1
f1
q2
f2
連接
f2
佐賀大学知能情報システム学科
9
図3.17(c)
最終状態が1個だけ
r1 のNFA
開始
q1
f1
*
開始
平成15年6月16日
q0
ε
ε
ε
q1
f1
ε
佐賀大学知能情報システム学科
f0
10
どんどんやってみる
1
q5
q7
開始
q１
0
q6
q２
ε
q3
0
やってみ
てね
*
q8
q4
+
q１
0
q２
ε
0
q3
連接
q4
1
1
q5
開始
0
0
開始
0
開始
平成15年6月16日
q１
q6
0
q２
開始
佐賀大学知能情報システム学科
q3
q4
11
NFAの生成例
正規表現 : 01*+1
1. 括弧つきに書き換える
r
01*+1 → ((0(1*))+1)
+
r1
2. 分解していく
1. r=r1+r2, r1=0(1*), r2=1
2. r1=r3r4, r3=0, r4=1*
3. r4=r5*, r5=1
r2
連接
r3
0
r4
*
1
r5
1
平成15年6月16日
佐賀大学知能情報システム学科
12
r
NFAの生成例
r1
(つづき 1)
正規表現 : 01*+1
3. 最小構成をFAに変換する
4. FAを組みあげていく
+
r3
0
連接
r4
*
1. r4=r5*, r5=1
q5
1
q6
2. r1=r3r4 , r3=0
開始
q3
0
q4
開始
q1
1
q2
平成15年6月16日
佐賀大学知能情報システム学科
1
r5
1
開始
3. r=r1+r2 , r2=1
r2
13
NFAの生成例
r
(つづき 2)
r1
4.1. r4=r5*
r3
連接
ε
ε
q5
1
r5=1
r2
r4
*
0
q7
+
1
r5
1
q6
ε
q8
ε
平成15年6月16日
佐賀大学知能情報システム学科
14
NFAの生成例
r
(つづき 3)
4.2. r1=r3r4
開始
r1
r3=0
0
q3
r3
0
q4
ε
q7
q5
連接
r2
r4
*
1
r5
1
ε
ε
+
1
r5=1
r4=r5*
q6
ε
q8
ε
平成15年6月16日
佐賀大学知能情報システム学科
15
r
NFAの生成例
ε
開始
q1
1
連接
r2
r4
*
0
r2=1
4.3. r=r1+r2
q9
r1
r3
(つづき 4)
+
1
r5
1
ε
q2
q10
ε
0
q3
ε
q4
ε
q7
ε
平成15年6月16日
ε
ε
q5
1
r5=1
q6
佐賀大学知能情報システム学科
r4=r5*
ε
q8
16
DFA→正則表現
(3.2.1項 p.100～)
考え方
1.ある状態からある状態の間の状態を0か
らひとつずつ増やしていって、
2.状態の任意の組からなる道が生成するこ
とのできる文字列の正則表現を再帰的に
拡張していき、
3.最後に、初期状態から最終状態への道が
生成できる文字列の正則表現を求める。
平成15年6月16日
佐賀大学知能情報システム学科
17
数学的に定義
Mの状態をqiから途中qjより大きな番号の
状態を通らずに、qjにたどり着くことのでき
る入力列の集合
Rijk Rikk 1 ( Rkkk 1*)Rkjk 1 Rijk 1 (k 1)
0
Rij {a | (qi , a ) q j } { } (i jのとき )
0
Rij {a | (qi , a ) q j } (i jのとき )
平成15年6月16日
佐賀大学知能情報システム学科
18
正則表現の式との対応
Rijk Rikk 1 ( Rkkk 1*)R kjk1 Rijk 1 (k 1)
0
Rij {a | (qi , a ) q j } { } (i jのとき )
0
Rij {a | (qi , a ) q j } (i jのとき )
↓
rijk rikk 1 (rkkk 1*)rkjk 1 rijk 1 (k 1)
0
rij a (i jのとき )
0
rij a (i jのとき )
平成15年6月16日
佐賀大学知能情報システム学科
19
正則表現の生成例その1
1
0
q1
0
1
q2
0,1
開始
δ
q3
r110 {a | (q1 , a ) q1}
(1 1)
r120 {a | (q1 , a ) q2 } 0
(1 2)
r130 {a | (q1 , a ) q3 } 1
(1 3)
r210 {a | (q2 , a ) q1} 0
(2 1)
r220 {a | (q2 , a ) q2 }
( 2 2)
(2 3)
0
1
q1
q2
q3
r230 {a | (q2 , a ) q3 } 1
q2
q1
q3
r310 {a | (q3 , a ) q1} φ
q3
q2
q2
r320 {a | (q3 , a ) q2 } 0 1
(3 2)
r330 {a | (q3 , a ) q3 }
(3 3)
平成15年6月16日
佐賀大学知能情報システム学科
(3 1)
20
どんどん進める
k=1
r r (r *)r r ( *)
1
11
0
11
0
11
0
11
0
11
r121 r110 (r110 *)r120 r120 ( *)0 0 0 0 0
r131 r110 (r110 *)r130 r130 ( *)1 1 1 1 1
r211 r210 (r110 *)r110 r210 0( *) 0 0 0 0
r221 r210 (r110 *)r120 r220 0( *)0 00
1
r231 r210 (r110 *)r130 r230 0( *)1 1 01 1
q1
r311 r310 (r110 *)r110 r310 φ( *) φφ
0
0
1
q2
0,1
q3
開始
r321 r310 (r110 *)r120 r320 φ( *)0 0 1 0 1
r331 r310 (r110 *)r130 r330 φ( *)1
平成15年6月16日
佐賀大学知能情報システム学科
21
どんどん進める
k=2
r r (r *)r r 0((00 )*)0 0(00) * 0 (00) *
2
11
1
12
1
22
1
21
1
11
r122 r121 (r221 *)r221 r121 0((00 )*)(00 ) 0 0(00) * 0 0(00) *
r132 r121 (r221 *)r231 r131 0((00 )*)(01 1) 1 0(00) * (0 )1 1
00*1 1 0 *1
r212 r221 (r221 *)r211 r211 (00 )((00 )*)0 0 (00) * 0 0 (00) * 0
r222 r221 (r221 *)r221 r221 (00 )((00 )*)(00 ) (00 )
(00) * 00 (00) *
1
r r (r *)r r (00 )((00 )*)(01 1) (01 1)
q1
2
23
1
22
1
22
1
23
1
23
0
(00) * (0 )1 01 1 0 *1 01 1 0 *1
r312 r321 (r221 *)r211 r311 (0 1)((00 )*)0 φ (0 1)(00) * 0
0
1
q2
0,1
q3
開始
r322 r321 (r221 *)r221 r321 (0 1)((00 )*)(00 ) (0 1)
(0 1)(00) * (0 1) (0 1)(00) *
r332 r321 (r221 *)r231 r331 (0 1)((00 )*)(01 1)
(0 1)(00) * (01 1) (0 1)(00) * (0 )1 (0 1)0 *1
平成15年6月16日
佐賀大学知能情報システム学科
22
最終状態への道
r123 r132 (r332 *)r322 r122
k=3
(0 *1)(((0 1)0 *1 )*)(0 1)(00) * 0(00) *
0 *1((0 1)0 *1) * (0 1)(00) * 0(00) *
1
0
q1
r133 r132 (r332 *)r332 r132
0
1
q2
0,1
q3
開始
0 *1(((0 1)0 *1 )*)((0 1)0 *1 ) (0 *1)
0 *1((0 1)0 *1) * ((0 1)0 *1 ) 0 *1
0 *1((0 1)0 *1) *
r123 r133 0 *1((0 1)0 *1) * (0 1)(00) * (00) * 0 *1((0 1)0 *1) *
0 *1((0 1)0 *1) * ((0 1)(00) * ) 0(00) *
平成15年6月16日
佐賀大学知能情報システム学科
23
まとめ方が難しい？
以下のルールを活用せよ
rs sr
(r s) t r ( s t )
(rs )t r ( st )
r ( s t ) rs rt
(r s )t rt st
平成15年6月16日
φ*
(r*)* r *
( r )* r *
(r * s*)* (r s) *
佐賀大学知能情報システム学科
24
正則表現の生成例その2
下の状態図に対応する正則表現を求めよ。
0
A
B
0
開始
平成15年6月16日
1
C
0
1
1
佐賀大学知能情報システム学科
25
とりあえず番号をつける
0
A
1
0
1
B
0
A
A
r110
A
B
r120 0
A
C
r130 1
B
A
r210 0
B
B
r220
C
r230 1
A
r310 1
B
r320 0
C
r330
C
1
開始
１から！
A→1
B→2
C→3
B
C
C
平成15年6月16日
C
佐賀大学知能情報システム学科
26
状態Aが加わった
k=1 その1
r111 r110 (r110 *)r110 r110 ( *)
ε
ε
A
ε
A
A
A
A
A
ε
ε
A
ε
A
A
A
A
ε
A
ε
A
A
r121 r110 (r110 *)r120 r120 ( *)0 0 0 0 0
ε
A
ε
A
A
A
A
ε
A
平成15年6月16日ε
A
B
ε
A
B
A
ε
A
ε
佐賀大学知能情報システム学科
A
B
27
状態Aが加わった
k=1 その2
r131 r110 (r110 *)r130 r130 ( *)1 1 1 1 1
ε
ε
A
ε
A
A
A
C
A
ε
ε
A
ε
A
A
A
C
ε
A
ε
A
C
r211 r210 (r110 *)r110 r210 0(0*) 0 00* 0 00*
ε
A
ε
B
A
B
A
ε
A
平成15年6月16日ε
A
A
ε
B
A
A
ε
A
ε
佐賀大学知能情報システム学科
A
A
28
状態Aが加わった
k=1 その3
r221 r210 (r110 *)r120 r220 0( *)0 00
ε
ε
A
ε
B
B
A
B
A
ε
ε
A
ε
A
A
B
B
ε
A
ε
A
B
r231 r210 (r110 *)r130 r230 0( *)1 1 011
ε
ε
A
ε
B
A
B
A
ε
A
平成15年6月16日ε
A
C
ε
B
C
A
ε
A
ε
佐賀大学知能情報システム学科
A
C
29
状態Aが加わった
k=1 その4
r311 r310 (r110 *)r110 r310 1( *) 1 1 1 1
ε
ε
A
ε
C
C
A
A
A
ε
ε
A
ε
A
A
C
A
ε
A
ε
A
A
r321 r310 (r110 *)r120 r320 1( *)0 0 10 0
ε
ε
A
ε
B
A
B
A
ε
A
平成15年6月16日ε
A
C
ε
B
C
A
ε
A
ε
佐賀大学知能情報システム学科
A
C
30
状態Aが加わった
k=1 その5
r331 r310 (r110 *)r130 r330 1( *)1 11
ε
ε
A
ε
C
C
A
C
A
ε
ε
A
ε
A
A
C
C
ε
A
ε
A
r
r 00*
r311 1
r 0
r 00
r321 10 0
r 1
r 01 1
r331 11
1
11
1
12
1
13
平成15年6月16日
1
21
1
22
1
23
佐賀大学知能情報システム学科
C
31
さらに状態Bが加わった
k=2 例1
r112 r121 (r221 *)r211 r111 0((00 )*)00*
0(00) * 00*
ε
ε
ε
A
B
ε
A
A
ε
ε
A
A
ε
平成15年6月16日
A
ε
A
A
ε
ε
ε
A
ε
ε
A
B
A
B
A
ε
ε
A
A
A
ε
ε
A
ε
ε
A
B
A
ε
A
佐賀大学知能情報システム学科
A
32
どんどん進める
k=2
r122 r121 (r221 *)r221 r121 0((00 )*)(00 ) 0 0(00) * 0 0(00) *
r132 r121 (r221 *)r231 r131 0((00 )*)(01 1) 1 0(00) * (0 )1 1
00*1 1 0 *1
r212 r221 (r221 *)r211 r211 (00 )((00 )*)00* 00* (00) * 00* 00*
(00) * 00*
r222 r221 (r221 *)r221 r221 (00 )((00 )*)(00 ) (00 ) (00) *
r232 r221 (r221 *)r231 r231 (00 )((00 )*)(01 1) (01 1)
((00) * )(01 1) (00) * (0 )1 0 *1
r312 r321 (r221 *)r211 r311 (10 0)((00 )*)00* 1 (10 0)(00) * 00* 1
r322 r321 (r221 *)r221 r321 (10 0)((00 )*)(00 ) (10 0)
(10 0)((00) * ) (10 0)(00) *
r332 r321 (r221 *)r231 r331 (10 0)((00 )*)(01 1) (11 )
(10 0)(00) * (0 )1 11 (10 0)0 *1 11
平成15年6月16日
佐賀大学知能情報システム学科
33
最終状態への道
k=3
r r123 r133
r211 (00) * 00*
r123 r132 ( r332 *)r322 r122
r221 (00) *
r r ( r *)r r
r231 0 *1
r111 0(00) * 00*
r312 (10 0)(00) * 00* 1
r122 0(00) *
r322 (10 0)(00) *
r131 0 *1
r332 (10 0)0 *1 11
3
13
2
13
平成15年6月16日
2
33
2
33
2
13
佐賀大学知能情報システム学科
34
最終解
k=3
r122 0(00 ) *
r322 (10 0)( 00 ) *
r131 0 *1
r332 (10 0)0 *1 11
r123 0 *1(((10 0)0 *1 11 )*)(10 0)(00) * 0(00) *
0 *1((10 0)0 *1 11) * (10 0)(00) * 0(00) *
0 *1(((10 0)0 *1) * (11)*)* (10 0)(00) * 0(00) *
r133 0 *1(((10 0)0 *1 11 )*)((10 0)0 *1 11 ) 0 *1
0 *1((10 0)0 *1 11) * 0 *1
0 *1(((10 0)0 *1) * (11)*)* 0 *1
r123 r133 0(00) * 0 *1( (((10 0)0 *1) * (11)*)* ( (10 0)(00)*))
平成15年6月16日
佐賀大学知能情報システム学科
35
状態消去法
(3.2.2項 p.105～)
状態を正則表現に順次置き換えていく
1. オートマトンの全ての辺のラベルを正則表現に書き
2.
3.
4.
5.
改める
受理状態qと開始状態q0のみを残して、後は消去す
る(消去法: p.106-107, 図3.7→図3.8)
q≠q0の場合には、この2状態オートマトンに図3.9(p.
108)のようなラベル付けをする
q=q0の場合には、この1状態オートマトンに図3.10(p.
109)のようなラベル付けをする
3と4の和から全体を求める
平成15年6月16日
佐賀大学知能情報システム学科
36
消去後のFAと正則表現
図3.9 p.108
S
q0
→(R+SU*T)*SU*
q
T
開始
R
U
図3.10 p.109
開始
→R*
q0
R
平成15年6月16日
佐賀大学知能情報システム学科
37
状態消去法の例
(例3.6 p.109)
末尾から2文字目か3文字目に1がある列
の全体を受理するFA
1
A
開始
平成15年6月16日
B
0,1
C
0,1
D
0,1
佐賀大学知能情報システム学科
38
ラベルの書き換え
正則表現に書き換える
1
A
開始
平成15年6月16日
B
0+1
C
0+1
D
0+1
佐賀大学知能情報システム学科
39
状態Bの消去
繰り返し作業を省くためこの時点で消去
A
1
0+1
B
φ
φ
A
開始
平成15年6月16日
φ+1φ*(0+1)
=1(0+1)
C
1(0+1)
C
0+1
D
0+1
佐賀大学知能情報システム学科
40
状態Cの消去
(A, D)の組用
A
1(0+1)
0+1
C
φ
開始
A
1(0+1)(1+0)
D
φ+1(0+1)φ*(0+1)
=1(0+1)(0+1)
φ
D
0+1 ((0+1)+1(0+1)(1+0)φ*φ)*(1(0+1)(0+1))φ*
=(0+1)*1(0+1)(1+0)
平成15年6月16日
佐賀大学知能情報システム学科
41
状態Dの消去
(A, C)の組用
C
開始
0+1
A
D
1(0+1)
0+1
平成15年6月16日
後続状態がない！
C
((0+1)+1(0+1)φ*φ)*(1(0+1))φ*
=(0+1)*1(0+1)
佐賀大学知能情報システム学科
42
最終的な正則表現
(A, C)と(A, D)の正則表現の和
→ (0+1)*1(0+1)+(0+1)*1(0+1)(0+1)
平成15年6月16日
佐賀大学知能情報システム学科
43
ミニテストと次回内容
ミニテスト
教科書・資料を見ても、友達と相談しても良い
15分後に指名された人は板書
ミニテストを提出すること
出したら帰って良し
次回(6/23)内容
DFAの最小化
平成15年6月16日
佐賀大学知能情報システム学科
44
© Copyright 2024 ExpyDoc
