スライド 1

形式言語とオートマト
第4回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定
形式言語とオートマト
本日の予定１
形式言語とオートマト
空動作とは？
空動作（ε-move）とは
入力記号を読まずに状態遷移できる
(つまりいつでも遷移してよい）
ε
S
ε
δ(S, ε) = P
形式言語とオートマト
P
Q
S
ε
δ(S, ε) = Q
R
δ(S, ε) = R
空動作を許す、とは？
0
p
ε
q
ε
r
1
入力無しでも二つの状態
形式言語とオートマト
q,rのどちらかに行ける
空動作を許す場合も動作関数を拡張して五字組で表
す
M  Q, , , q0 , F 
Q
状態の有限集合

入力記号の有限集合

動作関数
 : Q  ( { })  2
Q
q0  Q
q0
初期状態
F
受理状態の有限集合
形式言語とオートマト
注意
F Q
空動作を許す場合の五字組
M  Q, ,  , q0 , F 
Q  { p, q, r}
  {0,1}
0
 : Q  ( { })  2Q
 ( p,  )  {q, r},  ( p,0)   ( p,1)   ,
 (q,0)  {q},
 (q,1)   (q,  )   ,
 (r ,1)  {r},
 (r ,0)   (r ,  )  
q0  p
F  {q, r}
形式言語とオートマト
p

q

r
1
空動作を許す場合の動作例
・入力00に対するＭの動作
0
0 $
ε
0
q
p
ε
r
1
形式言語とオートマト
空動作の動作例
・入力00に対するＭの動作
0
場合１
0 $
0
ε
p
入力記号を読まずに状態遷移
２通り存在する
形式言語とオートマト
q
ε
場合２
r
1
空動作の動作例
・入力00に対するＭの動作
0
場合１
0 $
0
ε
p
受理できる
q
ε
r
1
形式言語とオートマト
空動作の動作例
・入力00に対するＭの動作
0
0 $
0
ε
p
これ以上遷移できない
→受理できない
形式言語とオートマト
q
ε
場合２
r
1
空動作の動作例
・入力00に対するＭの動作
0
0
0 $
ε
q
ε
r
p
1
入力語を読み終えたとき受理状態に到達する遷移が可能なので
入力語 00 は受理される。
形式言語とオートマト
空動作の動作例
・入力110に対するＭの動作
0
1 1 0 $
ε
q
p
ε
r
1
入力語を読み終えたとき受理状態に到達する遷移が不可能なので
入力語 110 は拒否される。
形式言語とオートマト
空動作のまとめ
空動作とは，入力記号を読まなくてもできる状態遷移
状態遷移は様々な場合が存在する
ε
Q
ε
R
S
(S, )  {Q, R}
形式言語とオートマト
形式言語とオートマト
本日の予定２
形式言語とオートマト
非決定性有限オートマトン(NFA)
→決定性有限オートマトン(DFA)
NFA（非決定性FSA）
a
a
b
a
r
DFA（決定性FSA）
s
a
t
b
{r}
a
{r,s}
b
δn
a
r
r, s r
s t
t -形式言語とオートマト
a
b
b
---
{p,q,r}
a
b
{r}
{r,s} {r}
{r,s} {r,s,t} {r}
{r,s,t} {r,s,t} {r}
非決定性有限オートマトン(NFA)
→決定性有限オートマトン(DFA)
NFA（非決定性FSA）
DFA（決定性FSA）
0
0

p

{q}
1
0
q
{∅}
{p,q,r}
r
1
1
形式言語とオートマト
0
{r}
1
0,1
DFAとNFAの同等性
教科書P.47
【例2.6】を読みましょう。
実際に図2.9を図2.13に変換してみよう。
※アルゴリズム2.1をじっくり読めば理解できます。
形式言語とオートマト
DFAとNFAの同等性
1. 𝑀𝑛 の状態の集合に応じて𝑀𝑑 の状態をつくる
a
a
r
s
a
t
𝑴𝒅 =
𝒓, 𝒔, 𝒕 , 𝒓, 𝒔 , 𝒔, 𝒕 , 𝒕, 𝒓 , 𝒓 , 𝒔 , 𝒕 , ∅
b
2. 𝑀𝑛 において入力を読まずに遷移できる状態を
𝑀𝑑 の初期状態とする
3. 𝑀𝑛 の受理状態を含む状態を𝑀𝑑 の受理状態とする
4. 教科書を読んでもわかりにくい・・・
形式言語とオートマト
DFAとNFAの同等性
1. 𝑀𝑛 の状態の集合に応じて𝑀𝑑 の状態をつくる
a
a
r
s
a
t
𝑴𝒅 =
𝒓, 𝒔, 𝒕 , 𝒓, 𝒔 , 𝒔, 𝒕 , 𝒕, 𝒓 , 𝒓 , 𝒔 , 𝒕 , ∅
b
2. 𝑀𝑛 において入力を読まずに遷移できる状態を
𝑀𝑑 の初期状態とする
3. 𝑀𝑛 の受理状態を含む状態を𝑀𝑑 の受理状態とする
4. 教科書を読んでもわかりにくい・・・
形式言語とオートマト
DFAとNFAの同等性
要は入力によって何処に遷移するかを見るだけ!!
rにaが入力された場合
r 又は sに遷移する
⇒ {r,s}という名前を
持つ状態に遷移す
ると考える
a
a
r
s
a
t
{r}
{r,s}
b
形式言語とオートマト
a
b
{r,s}
{r}
{r,s,t} {r}
{r,s,t} {r,s,t} {r}
DFAとNFAの同等性
要は入力によって何処に遷移するかを見るだけ!!
rにaが入力された場合
r 又は sに遷移する
a
a
r
s
a
⇒ {r,s}という名前を
持つ状態に遷移す
ると考える
t
a
b
a
r
b
形式言語とオートマト
a
s
a
tt
{r}
{r,s}
b
{r,s} {r}
{r,s,t} {r}
{r,s,t} {r,s,t} {r}
DFAとNFAの同等性
要は入力によって何処に遷移するかを見るだ
け!!にaが入力された場合
{r,s}
r 又は s 又は t に遷移する
⇒ {r,s,t}という名前の状態
に遷移すると考える
a
a
r
s
a
t
b
a
a
r
s
a
t
{r}
a
b
{r,s}
{r}
{r,s} {r,s,t} {r}
{r,s,t} {r,s,t} {r}
b
形式言語とオートマト
初期状態から到達できる状態だけで良
い
NFA→DFA
遷移先がない場合も
複数ある場合もある
遷移先が
一意に決定
a
a
r
a
b
s
a
t
b
{r}
b
δn
a
r
r, s r
s t
t -形式言語とオートマト
a
b
---
a
{r,s}
{p,q,r}
b
a
b
{r}
{r,s} {r}
{r,s} {r,s,t} {r}
{r,s,t} {r,s,t} {r}
NFAを同等なDFAに
書き換えるアルゴリズム
教科書P.50
【例2.7】を読みましょう。
実際に図2.11を図2.14に変換してみよう。
※アルゴリズム2.2をじっくり読めば理解できます。
形式言語とオートマト
空動作のある場合
1. 初期状態の構成
入力を読まなくてもq, rに遷移可能
初期状態 𝑭𝒅 = 𝒑, 𝒒, 𝒓
0
p

q

r
{p,q,r}
1
形式言語とオートマトン
空動作のある場合
1. 初期状態の構成
NFAの初期状態pから入力なし
で q または r に遷移できる
DFAの初期状態は
{p.q.r} となる
0
p

q

r
{p,q,r}
1
形式言語とオートマトン
空動作のある場合
1. 初期状態の構成
NFAの初期状態pから入力なし
で q または r に遷移できる
0
p

q

r
{p,q,r}
1
形式言語とオートマトン
DFAの初期状態は
{p.q.r} となる
空動作のある場合
2. アルゴリズム2.1と同様に状態遷移をつくる
0
p

q

r
{p,q,r}
1
形式言語とオートマト
空動作のある場合
2. アルゴリズム2.1と同様に状態遷移をつくる
0
0
p

q

r
{q}
1
0
∅
{p,q,r}
1
1
形式言語とオートマト
0
{r}
1
0,1
空動作のある場合
3. 受理状態を含む部分集合に対応する状態を
受理状態とする
0
0
p

q

r
{q}
1
0
∅
{p,q,r}
1
1
形式言語とオートマト
0
{r}
1
0,1
空動作のある場合
3. 受理状態を含む部分集合に対応する状態を
受理状態とする
0
0
p

q

r
{q}
1
0
∅
{p,q,r}
1
1
形式言語とオートマト
0
{r}
1
0,1
NFA→DFA
遷移先が一意に決定
遷移先が不確定
0

p
δn

ε
0
1
p
q,r
q
r
p
--
q
--
r
--
--
r
形式言語とオートマト
0
{q}
q
0
∅
{p,q,r
}
r
1
1
δd
1
{r}
0
1
0
1
{p,q,r}
{q}
{r}
{q}
{q}
Φ
{r}
Φ
[r]
Φ
Φ
Φ
0,
1
DFAとNFAの同等性まとめ
・決定性有限オートマトン(DFA)
同等（同じ仕事をする）
・非決定性有限オートマトン(NFA)
・空動作を許す非決定性有限オートマトン（NFA)
アルゴリズム2.1や2.2を使って書き換えられる
形式言語とオートマト
頭の整理のために
小テストを行いましょう。
形式言語とオートマト

Download Report