(NFA)を同等な決定性オートマトン(DFA)

Report
形式言語 と オートマトン
第4回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定
形式言語とオートマトン
(-) から  を構成する方法を学ぶ!!
NFA(非決定性FSA)
形式言語とオートマトン
DFA(決定性FSA)
アルゴリズム 2.1
の
復習
形式言語とオートマトン
アルゴリズム 2.1
説明しやすいため,
遷移図を5字組化
 = {, , }
Σ = {, }
 :  × Σ → 2
a
 ,  = ,  ,  ,  =  ,
 ,  =  ,
 ,  =  ,
 ,  =  ,
 ,  = 
0 = 
 = {}
形式言語とオートマトン
a
r
b
s
a
t
1.  の状態の集合の部分集合に全体で、
 の状態( )をつくる
 = { , ,  , ,  , ,  , ,  ,  ,  ,  ,  }
{r,s,t}
{r,s}
{r}
{s,t}
{s}
{t,r}
{t}
形式言語とオートマトン

2.  において入力を読まずに遷移できる状態の集合を
 の初期状態(0 )とする
0 = {}
{r,s,t}
{r,s}
{r}
{s,t}
{s}
{t,r}
{t}
形式言語とオートマトン

3.  の受理状態を1つでも含む部分集合に対する状態を
 の受理状態とする
 = {
{r,s,t}
, ,  , ,  , ,  , 
{r,s}
{r}
{s,t}
{s}
{t,r}
{t}
形式言語とオートマトン
}

4. の動作関数( )を決める
 {, , },  = {, , }
{r,s,t}
a
b
 {, , },  =
{r,s}
{r}
{s,t}
{s}
{t,r}
{t}
形式言語とオートマトン
{}

アルゴリズム 2.1 の 4
全ての動作関数を求める
a
b
{r,s}
{r}
b
a,b
a
{r,s,t}
b
{s,t}
a
a
形式言語とオートマトン
b
{s}
b
{t,r}
a
b
a
{t}
a,b

5. の初期状態から到達できない状態(遷移)をすべて削除
a
b
{r,s}
{r}
b
, 
a
{r,s,t}
b
{s,t}
a
a
形式言語とオートマトン


{t,r}
{s}
a

a
{t}
, 
∅
アルゴリズム 2.1
a
{r,s}
b
{r}
b
a
{r,s,t}
b
a
b
{r} a
a
{r,s} a
b
b
形式言語とオートマトン
{r,s,t}
NFA
DFA
する理由は?
NFA(非決定性FSA)
a
DFA(決定性FSA)
a
b
a
r
s
a
t
{r} a
{r,s} a
b
b
形式言語とオートマトン
b
{r,s,t}
NFA
遷移先がなかったり
複数あったり…
DFA
遷移先が唯一
a
b
a
a
r
s
a
{r}
t
a
{r,s} a
{r,s,t}
b
b
b

r
s
t
a
r, s
t
--
形式言語とオートマトン
b
r
---

a
b
{r}
{r,s}
{r}
{r,s}
{r,s,t}
{r}
{r,s,t}
{r,s,t}
{r}
アルゴリズム 2.2 を学ぶ
形式言語とオートマトン
アルゴリズム 2.2
NFA(非決定性FSA)
DFA(決定性FSA)
0

q

r
p
空動作
がある
形式言語とオートマトン
0
{q}
1
0
{p,q,r}
1

1
0
1
{r}
0,1
まず、NFAを五字組化
M n  Q n ,  n ,  n , q 0 n , Fn 
Q n  { p , q , r}
 n  { 0 ,1}
0
 n : Q n  (  n  { })  2
Qn
 n ( p ,  )  { q , r },  n ( p , 0 )   n ( p ,1)   ,
 n ( q , 0 )  { q },
 n ( q ,1)   n ( q ,  )   ,
 n ( r ,1)  { r },
 n ( r ,0 )   n ( r ,  )  
q0n  p
Fn  { q , r }
形式言語とオートマトン

q

r
p
1
1.  において初期状態から入力を読まずに遷移できる状
態の集合に対応して、  の初期状態(0 )とする
0
p
ε
ε
q
r
1
入力を読まなくてもq, rに遷移可能
形式言語とオートマトン
初期状態  = , , 
 = , , 
{p,q,r}
形式言語とオートマトン
2.  の初期状態(0 )について、各入力記号 ∈ Σにおけ
  { 0 ,1}
る状態遷移を決める
 (, 0) ∪  (, 0) ∪  , 0 = {}
さらに から入力を読まずに遷移できる状態はない
 , ,  , 0 = {}
新状態
 (, 1) ∪  (, 1) ∪  , 1 = {}
さらに から入力を読まずに遷移できる状態はない
 , ,  , 1 = {}
新状態
 n ( p ,  )  { q , r },  n ( p , 0 )   n ( p ,1)   ,
 n ( q , 0 )  { q },
 n ( q ,1)   n ( q ,  )   ,
 n ( r ,1)  { r },
 n ( r ,0 )   n ( r ,  )  
形式言語とオートマトン
 , ,  , 0 = {}
 , ,  , 1 = {}
新状態  ,  をつくり
{q}
0
{p,q,r}
1
{r}
形式言語とオートマトン
手順2.をまた実行する、新状態の状態遷移を決める
  , 0 =  (, 0) = {}
  , 1 =  , 1 = ∅
  , 0 =  , 0 = ∅
新状態
  , 1 =  , 1 = {}
 n ( p ,  )  { q , r },  n ( p , 0 )   n ( p ,1)   ,
 n ( q , 0 )  { q },
 n ( q ,1)   n ( q ,  )   ,
 n ( r ,1)  { r },
 n ( r ,0 )   n ( r ,  )  
形式言語とオートマトン
新状態  をつくり
0
{q}
1
0
{p,q,r}

1
0
1
{r}
形式言語とオートマトン
手順2.をまた実行する、新状態の状態遷移を決める
 ∅, 0 = ∅
 ∅, 1 = ∅
これ以上、新たに状態が作られなかったので、手順2.を
終わる
形式言語とオートマトン
0
{q}
1
0
{p,q,r}

1
0
1
{r}
形式言語とオートマトン
0,1
3.  の受理状態を1つでも含む部分集合に対する状態を
 の受理状態とする
Fn  { q , r }
 = {
, ,  ,  , 
形式言語とオートマトン
}
 = {
, ,  ,  , 
}
0
{q}
1
0
{p,q,r}

1
0
1
{r}
形式言語とオートマトン
0,1
アルゴリズム 2.1 と アルゴリズム 2.2 の比較
5ステップ
3ステップ
使いやすい
形式言語とオートマトン
DFAとNFAの同等性まとめ
・決定性有限オートマトン(DFA)
同等(同じ仕事をする)
・非決定性有限オートマトン(NFA)
・空動作を許す非決定性有限オートマトン(NFA)
アルゴリズム2.1や2.2を使って書き換えられる
形式言語とオートマトン
形式言語とオートマトン
定義
 同じ言語を受理するDFAの
中でも状態数の一番少ない
DFAを最簡形のDFAという
形式言語とオートマトン
  から最簡形の  を構成する
アルゴリズム 2.3 を学ぶ
形式言語とオートマトン
お疲れ様
小テストです
形式言語とオートマトン

similar documents