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

計算の理論 I
ー正則表現とFAの等価性その2ー
月曜３校時
大月美佳
連絡事項
 自転車がまだ散乱してますね
今日の講義内容
1. 前回のミニテスト
1. ミニテストの解答例
2. 正則表現からDFAまで変換してみる
3. 今日の新しいこと
1. 正則表現とFAの等価性つづき
1. 正則表現からのε-動作を含むNFAの作り方
→ 例2.12 (p. 42)
2. DFAからの正則表現の作り方
→ 例2.13 (p. 45)
前回のミニテスト
(演習問題 2.12, p. 66)
次の正則表現と同値な有限オートマトンを
構成せよ。
a) 10+(0+11)0*1
1. 括弧でくくってみる
((10)+(((0+(11))(0*))1) : 左優先
((10)+((0+(11))((0*)1)) : 右優先
構文木
((10)+(((0+11)(0*))1)
((10)+((0+11)((0*)1))
+
+
連接
1
連接
連接
0
+
0
1
1
連接
1
0
連接
0
+
0
連接
*
連接
1
連接
1
1
*
0
1
最初の組合せで考えてみる
r
+
r1
連接
r3
1
r2
0
連接
r5
r4
連接
r7
r9
0
1
+
* r8
r10
連接
0
r12 1
1 r13
r6
r11
式の分解
r
+
r1
連接
r3
1
0
r2
連接
r5
r4
連接
r7
r9
0
r12
1
+
* r8
r10
連接
0
1
1
r6
r13
r11
r=r1+r2
r1 =r3r4
r2 =r5r6
r3 =1
r4 =0
r5 =r7r8
r6 =1
r7 =r9 + r10
r8 =r11*
r9 =0
r10 =r12r13
r11 =0
r12 =1
r13 =1
どんどん変換していこう
1
r
r12
+
r1
連接
r3
1
0
r2
連接
r5
r4
連接
r7
r9
0
r12
* r8
r10
連接
0
1
1
1
q１
1
q２
q3
q4
r6
1
+
r13
開始
開始
r11
連接
r13
r10
ε
1
q１
開始
q２
1
q3
q4
どんどん変換していこう
2
r10
r9
q5
q１
q6
q２
1
q3
q4
開始
開始
r
ε
1
0
+
r1
連接
r3
1
0
r2
連接
r5
r4
連接
r7
r9
r12
1
r6
1
r7
* r8
+
r10
連接
0
+
1
0
r13
ε
r11
q7
開始
ε
q5
q２
ε
q6
q8
ε
1
q１
0
1
q3
q4
ε
どんどん変換していこう
3
r
r11
+
r1
連接
r3
1
0
r2
連接
r5
r4
連接
r7
r9
0
r12
* r8
r10
連接
0
1
q10
r6
1
+
1
0
q9
開始
r11
*
r13
r8
ε
ε
開始
q11
ε
0
q9
q10
ε
q12
どんどん変換していこう
4
r7
ε
q7
ε
q5
q２
ε
q8
q11
1
q3
q4
ε
開始
ε
q6
ε
1
q１
0
r8
ε
0
q9
ε
q10
q12
ε
開始
連接
ε
q7
開始
ε
q5
r5
q２
ε
q6
ε
ε
q8
ε
1
q１
0
ε
q11
q9
q10
1
q3
q4
ε
ε
0
ε
q12
どんどん変換していこう
5
ε
q7
0
q5
q１
1
q13
q8
q3
ε
q4
ε
開始
連接
ε
ε
q11
ε
0
q9
q14
1
q２
開始
r6
ε
q6
ε
1
ε
r5
q10
r2
q12
ε
ε
q7
ε
q5
0
q8
ε
1
q１
1
q２
開始
ε
q6
q3
ε
q4
ε
ε
q11
q9
ε
ε
0
q10
ε
q12
1
q13
q14
どんどん変換していこう
6
r
r3
+
r1
連接
r3
1
0
r2
連接
r5
r4
連接
r7
r9
0
r12
* r8
r10
連接
0
1
1
1
q15
0
q16
q17
q18
r6
1
+
r4
開始
開始
r11
連接
r13
r1
ε
1
q１5
開始
q16
1
q17
q18
これで（やっと）完成！
r1
ε
1
r
q１5
ε
q１9
開始
r2
ε
q7
ε
1
q16
ε
q5
q17
q１
ε
q20
0
ε
q6
q8
ε
1
q18
1
q２
q3
ε
q4
ε
ε
ε
q11
q9
ε
ε
0
q10
ε
q12
1
q13
q14
オートマトンとして真面目に書く
δ
 M(Q, {0, 1}, δ, q19,
{q20})
 Q={q1, q2, q3, q4, q5,
q6, q7, q8, q9, q10,
q11, q12, q13, q14, q15,
q16, q17, q18, q19,
q20}
 δ は右表
0
1
ε
q1
-
q2
-
q2
-
-
q3
q3
-
q4
-
q4
-
-
q8
q5
q6
-
-
q6
-
-
q8
q7
-
-
q1 , q 5
q8
-
-
q11
q9
q10
-
-
q10
-
-
q9 , q12
q11
-
-
q13
q12
-
-
q13
q13
-
q14
-
q14
-
-
q20
q15
-
q16
q16
-
-
q17
-
q18
q18
-
-
q20
q19
-
-
q7 , q15
q20
-
-
-
q17
ε
-
前回の例2.12の表記
q0
ε
q1
ε
q3
q2
1
0
q9
ε
q4
ε
ε
ε
q5
ε
q6
1 q7 ε
q8
ε
 M(Q, {0, 1}, δ, q0, {q9})
 Q={q1, q2, q3, q4, q5,
q6, q7, q8, q9}
 δ は右表
δ
0
1
ε
q0
-
-
{q１ }
q1
-
{q2 }
-
q2
-
-
{q9 }
q3
{q4 }
-
-
q4
-
-
{q5 }
q5
-
-
{q6 ,
q8}
q6
-
{q7 }
-
q7
-
-
{q7,
q8}
q8
-
-
{q9 }
q9
-
-
-
εありNFAから
εなしNFAを生成してみる
q0
開始
ε
q1
ε
q3
q2
1
0
q9
ε
q4
ε
ε
ε
q5
ε
q6
1 q7 ε
q8
ε
ε-CLOSURE(q1)={q1}
ε-CLOSURE(q2)={q2 , q9}
ε-CLOSURE(q3)={q3}
ε-CLOSURE(q4)={q4 , q5 , q6 , q8 , q9}
 - CLOSUREが Fの元を含むとき
 F  {q0 }
F  
そうでないとき
F
 (q, a)  ˆ (q, a) (q  Q, a  )
ˆ (q , a)    CLOSURE( (ˆ (q ,  ), a))
i
ε-CLOSURE(q0)={q0, q1, q3}
i
ˆ (qi ,  )    CLOSURE(qi )
ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ε-CLOSURE(q5)={q5 , q6 , q8 , q9}
ε-CLOSURE(q6)={q6 }
ε-CLOSURE(q7)={q7 , q6 , q8 , q9}
ε-CLOSURE(q8)={q8 , q9}
ε-CLOSURE(q9)={q9}
δ´を求める
q0について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q0 ,0)    CLOSURE( (  CLOSURE(q0 ),0))
   CLOSURE( ({q0 , q1 , q3},0))
   CLOSURE( (q0 ,0)   (q1 ,0)   (q3 ,0))
   CLOSURE(○○{q4 })
   CLOSURE(q4 )  {q4 , q5 , q6 , q8 , q9 }
ˆ (q0 ,1)    CLOSURE( (  CLOSURE(q0 ),1))
   CLOSURE( ({q0 , q1 , q3},1))
   CLOSURE( (q0 ,1)   (q1 ,1)   (q3 ,1))
   CLOSURE(○{q2 } ○)
   CLOSURE(q2 )  {q2 , q9 }
δ´を求める
q1について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q1 ,0)    CLOSURE( (  CLOSURE(q1 ),0))
   CLOSURE( ({q1},0))
   CLOSURE( (q1 ,0))
   CLOSURE(○)
○
ˆ (q1 ,1)    CLOSURE( (  CLOSURE(q1 ),1))
   CLOSURE( ({q1},1))
   CLOSURE( (q1 ,1))
   CLOSURE({q2 })
   CLOSURE(q2 )  {q2 , q9 }
δ´を求める
q2について
 (qi , a )  ˆ (qi , a )    CLOSURE( (  CLOSURE(qi ), a ))
ˆ (q2 ,0)    CLOSURE( (  CLOSURE(q2 ),0))
   CLOSURE( ({q2 , q9 },0))
   CLOSURE( (q2 ,0)   (q9 ,0))
   CLOSURE(○○)
   CLOSURE(○) ○
ˆ (q2 ,1)    CLOSURE( (  CLOSURE(q2 ),1))
   CLOSURE( ({q2 , q9 },1))
   CLOSURE( (q2 ,1)   (q9 ,1))
   CLOSURE(○○)
   CLOSURE(○) ○
δ´を求める
q3について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q3 ,0)    CLOSURE( (  CLOSURE(q3 ),0))
   CLOSURE( ({q3},0))
   CLOSURE( (q3 ,0))
   CLOSURE({q4 })
   CLOSURE(q4 )  {q4 , q5 , q6 , q8 , q9 }
ˆ (q3 ,1)    CLOSURE( (  CLOSURE(q3 ),1))
   CLOSURE( ({q3},1))
   CLOSURE( (q3 ,1))
   CLOSURE(○)
○
δ´を求める
q4について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q4 ,0)    CLOSURE( (  CLOSURE(q4 ),0))
   CLOSURE( ({q4 , q5 , q6 , q8 , q9 },0))
   CLOSURE( (q4 ,0)   (q5 ,0)   (q6 ,0)   (q8 ,0)   (q9 ,0))
   CLOSURE(○○○○○)
   CLOSURE(○) ○
ˆ (q4 ,1)    CLOSURE( (  CLOSURE(q4 ),1))
   CLOSURE( ({q4 , q5 , q6 , q8 , q9 },1))
   CLOSURE( (q4 ,1)   (q5 ,1)   (q6 ,1)   (q8 ,1)   (q9 ,1))
   CLOSURE(○○{q7 } ○○)
   CLOSURE(q7 )  {q7 , q6 , q8 , q9 }
δ´を求める
q5について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q5 ,0)    CLOSURE( (  CLOSURE(q5 ),0))
   CLOSURE( ({q5 , q6 , q8 , q9 },0))
   CLOSURE( (q5 ,0)   (q6 ,0)   (q8 ,0)   (q9 ,0))
   CLOSURE(○○○○)
   CLOSURE(○) ○
ˆ (q5 ,1)    CLOSURE( (  CLOSURE(q5 ),1))
   CLOSURE( ({q5 , q6 , q8 , q9 },1))
   CLOSURE( (q5 ,1)   (q6 ,1)   (q8 ,1)   (q9 ,1))
   CLOSURE(○{q7 } ○○)
   CLOSURE(q7 )  {q6 , q7 , q8 , q9 }
δ´を求める
q6について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q6 ,0)    CLOSURE( (  CLOSURE(q6 ),0))
   CLOSURE( ({q6 },0))
   CLOSURE( (q6 ,0))
   CLOSURE(○)
○
ˆ (q6 ,1)    CLOSURE( (  CLOSURE(q6 ),1))
   CLOSURE( ({q6 },1))
   CLOSURE( (q6 ,1))
   CLOSURE(q7 )
 {q6 , q7 , q8 , q9 }
δ´を求める
q7について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q7 ,0)    CLOSURE( (  CLOSURE(q7 ),0))
   CLOSURE( ({q6 , q7 , q8 , q9 },0))
   CLOSURE( (q6 ,0)   (q7 ,0)   (q8 ,0)   (q9 ,0))
   CLOSURE(○○○○)
   CLOSURE(○) ○
ˆ (q7 ,1)    CLOSURE( (  CLOSURE(q7 ),1))
   CLOSURE( ({q6 , q7 , q8 , q9 },1))
   CLOSURE( (q6 ,1)   (q7 ,1)   (q8 ,1)   (q9 ,1))
   CLOSURE({q7 } ○○○)
   CLOSURE(q7 )  {q6 , q7 , q8 , q9 }
δ´を求める
q8について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q8 ,0)    CLOSURE( (  CLOSURE(q8 ),0))
   CLOSURE( ({q8 , q9 },0))
   CLOSURE( (q8 ,0)   (q9 ,0))
   CLOSURE(○○)
   CLOSURE(○) ○
ˆ (q8 ,1)    CLOSURE( (  CLOSURE(q8 ),1))
   CLOSURE( ({q8 , q9 },1))
   CLOSURE( (q8 ,1)   (q9 ,1))
   CLOSURE(○○)
   CLOSURE(○) ○
δ´を求める
q9について
 (qi , a)  ˆ (qi , a)    CLOSURE( (  CLOSURE(qi ), a))
ˆ (q9 ,0)    CLOSURE( (  CLOSURE(q9 ),0))
   CLOSURE( ({q9 },0))
   CLOSURE( (q9 ,0))
   CLOSURE(○)
○
ˆ (q9 ,1)    CLOSURE( (  CLOSURE(q9 ),1))
   CLOSURE( ({q9 },1))
   CLOSURE( (q9 ,1))
   CLOSURE(○)
○
生成されたNFA
δ´
M´(Q´, {0,1},δ´,q0,{q9})
Q´={q0, q1, q2, q3, q4, q5, q6, q7,
q8, q9}
δ ´は右表
0
1
q0
{q4 , q5 , q6 , q8 , q9}
{q2 , q9}
q1
-
{q2 , q9}
q2
-
-
q3
{q4 , q5 , q6 , q8 , q9}
-
q4
-
{q6 , q7 , q8 , q9}
q5
-
{q6 , q7 , q8 , q9}
q6
-
{q6 , q7 , q8 , q9}
q7
-
{q6 , q7 , q8 , q9}
q8
-
-
q9
-
-
さらにDFAへ変換してみる
δ´
δ´´
0
1
0
1
q0
{q4 , q5 , q6 , q8 ,
q9}
{q2 , q9}
[q0 ]
[q4 , q5 , q6 , q8 , q9]
[q2 , q9]
q1
-
{q2 , q9}
[q4 , q5 , q6 , q8 ,
q9]
-
[q6 , q7 , q8 , q9]
q2
-
-
[q2 , q9]
-
-
q3
{q4 , q5 , q6 , q8 ,
q9}
-
[q6 , q7 , q8 , q9]
-
[q6 , q7 , q8 , q9]
q4
-
{q6 , q7 , q8 ,
q9}
q5
-
{q6 , q7 , q8 ,
q9}
q6
-
{q6 , q7 , q8 ,
q9}
q7
-
{q6 , q7 , q8 ,
q9}
q8
-
-
q9
-
-
M´´ (Q´´, {0,1},δ´´,[q0 ],F)
Q´´={[q0 ], [q4, q5, q6, q8, q9 ],
[q2, q9 ], [q6, q7, q8, q9 ]}
δ´´は上表
F= {[q4, q5, q6, q8, q9 ], [q2, q9 ],
[q6, q7, q8, q9 ]}
もとの正則表現と比べてみる
δ´´
[q2 , q9]
0
1
[q0 ]
[q4 , q5 , q6 , q8 , q9]
[q2 , q9]
[q4 , q5 , q6 , q8 ,
q9]
-
[q6 , q7 , q8 , q9]
[q2 , q9]
-
-
[q6 , q7 , q8 , q9]
-
[q6 , q7 , q8 , q9]
1
[q0 ]
0
[q4 ,q5 ,q6 ,q8 ,q9]
1
開始
[q4 ,q5 ,q6 ,q8 ,q9]
1
01*+1
今日の新しいこと
1. 正則表現とFAの等価性
NFA
ε-動作を含む
NFA
DFA
正則表現
1.
正則表現からのε-動作を含むNFAの作り方
先週やった
→NFAの生成例 (例2.12, p. 42)
2.
DFAからの正則表現の作り方
→正則表現の生成例 (例2.13, p. 45)
DFAからの正則表現の作り方
考え方
1.ある状態からある状態の間の状態を0か
らひとつずつ増やしていって、
2.途中の状態の任意の組からなる道が生
成することのできる文字列の正則表現を
再帰的に拡張していき、
3.最後に、初期状態から最終状態への道が
生成できる文字列の正則表現を求める。
状態を増やしていくとは？
q１
…
qn
…
q1
qs
k=2
qn
qn
…
qe
k=0
…
q1
qn
q1
q2
qs
qe
k=1
qs
qs
qe
qe
k=n
 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のとき )
正則表現の式との対応
 Rijk  Rikk 1 ( Rkkk 1*)R kjk1  Rijk 1 (k  1)
 0
 Rij  {a |  (qi , a )  q j }  { } (i  jのとき )
 0
 Rij  {a |  (qi , a )  q j } (i  jのとき )
↓ 証明はp.44～45
rijk  rikk 1 (rkkk 1*)rkjk 1  rijk 1 (k  1)
 0
rij  a   (i  jのとき )
 0
rij  a (i  jのとき )
正則表現の生成例
(例2.13, p. 45)
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)
0
1
q1
q2
q3
r230  {a |  (q2 , a )  q3 }  1
(2  3)
q2
q1
q3
r310  {a |  (q3 , a )  q1} ○
(3  1)
q3
q2
q2
r320  {a |  (q3 , a )  q2 }  0  1
(3  2)
r330  {a |  (q3 , a )  q3 }    
(3  3)
どんどん進める
1
k=1
r  r (r *)r  r   ( *)    
1
11
0
11
0
11
0
11
0
11
0
q1
開始
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  
r231  r210 (r110 *)r130  r230  0( *)1  1  01 1
r311  r310 (r110 *)r110  r310 ○( *) ○○
r321  r310 (r110 *)r120  r320 ○( *)0  0  1  0  1
r331  r310 (r110 *)r130  r330 ○( *)1    
0
1
q2
0,1
q3
どんどん進める
k=2
1
0
q1
r112  r121 (r221 *)r211  r111  0((00   )*)0    0(00) * 0    (00) * 開始
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) *
r232  r221 (r221 *)r231  r231  (00   )((00   )*)(01 1)  (01 1)
 (00) * (0   )1  01 1  0 *1  01 1  0 *1
r312  r321 (r221 *)r211  r311  (0  1)((00   )*)0 ○ (0  1)(00) * 0
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  
0
1
q2
0,1
q3
最終状態への道
1
k=3
r  r (r *)r  r
3
12
2
13
2
33
2
32
2
12
 (0 *1)(((0  1)0 *1   )*)(0  1)(00) * 0(00) *
 0 *1((0  1)0 *1) * (0  1)(00) * 0(00) *
0
q1
0
1
q2
0,1
q3
開始
r133  r132 (r332 *)r332  r132
 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) *
今日のミニテスト
 ミニテスト
– 演習問題 2.13のa
– 教科書・資料を見ても良い
 資料、ミニテストがない人は前へ
 提出したら帰って良し
 次回
– 3章いきます。反復補題。

Download Report