非決定性有限オートマトン

形式言語 と オートマト
第3-2回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
有限オートマトン
(Finite State Automata:
FSA)
の
5字組による表示
形式言語とオートマト
有限オートマトン
(Finite State Automata:
FSA)
FSA: M = <Q, Σ, d, q, F> の5字組
・ Q : 状態の集合
・ Σ : 使用するアルファベット
・ d : 動作関数
・ q :初期状態
・ F : 受理状態の集合
形式言語とオートマト
有限オートマトンの例
M = <Q, Σ, d, q, F>
Q  {r , s, t}
  {a, b}
 :Q  Q
 ( r , a )  s,  ( r , b)  r ,
 ( s, a )  t ,  ( s, b)  r ,
 (t , a )  t ,  (t , b)  r
q0  r
F  {t}
形式言語とオートマト
b
r
a
b
s
a
b
t
a
有限オートマトン
(Finite State Automata:
FSA)
の変遷を様相を使って見る
様相(configuration)=時点表示
形式言語とオートマト
様相でオートマトンの変遷を
追う
様相の定義=(オートマトンの状態,未読の入力)
オートマトンの動作に従い、状態が変化する
未読入力が減ってゆく
->> 最後に (終状態, 空列)となったら受理、
そうでなければ受理しない
形式言語とオートマト
入力abbaが受理されるかどう
かを
様相(configuration)を使って調べる
1. 文字列 M = abaaを入力
2. これを1文字ずつ読んで行く
3. 読み終わったら$が入力される(εは空列)
4. その状態で受理状態のどこかにいれば
Mは受理される
形式言語とオートマト
|
様相(configuration)の変遷
(q 0 , a1a 2 a 3    a n ) (q1 , a 2 a 3    a n ) 
M
M
(q1 , a 3    a n )    (q n , )
M
M
*
(q0 , a1a2 a3    an ) (qn ,  )
M
形式言語とオートマト
“有限オートマトンの例”
で示したオートマトンMにabaaを入力し
てみる
M = <Q, Σ, d, q, F>
Q  {r , s, t}
  {a, b}
 :Q  Q
 ( r , a )  s,  ( r , b)  r ,
 ( s, a )  t ,  ( s, b)  r ,
 (t , a )  t ,  (t , b)  r
q0  r
F  {t}
形式言語とオートマト
(r , abba) ( s, bba) 
M
M
(r , ba) (r , a) ( s,  )
M
M
受理状態でない s で終了
→拒否
“有限オートマトンの例”
で示したオートマトンMにaaaaを入力し
てみる
M = <Q, Σ, d, q, F>
(r , aaaa) ( s, aaa) 
Q  {r , s, t}
  {a, b}
 :Q  Q
 ( r , a )  s,  ( r , b)  r ,
 ( s, a )  t ,  ( s, b)  r ,
 (t , a )  t ,  (t , b)  r
q0  r
F  {t}
形式言語とオートマト
M
M
(t , aa) (t , a) (t ,  )
M
M
受理状態 t で終了
→受理
非決定性FAの様相(=時点表示)
状態rでa を入力すると遷移は2種類
( r , aab )  ( r , ab )  ( r , b)  ( r , ε )
M
M
M
 ( r , ab )  (s, b) ?
M
M
受理状態でないrで入力が尽きるか、
状態sでbを読めない、のどちらにし
てもaabは受理されない
形式言語とオートマト
a
a
r
b
s
a
t
形式言語とオートマト
非決定性有限オートマトンとは!?
(前回までの授業)
決定性有限オートマトン
すべての状態ですべての入力に対して、
遷移先が唯一
a
形式言語とオートマト
非決定性有限オートマトンとは!?
非決定性有限オートマトン
一つの入力に対し、遷移先が唯一でない
a
a
形式言語とオートマト
非決定性有限オートマトンとは!?
非決定性有限オートマトン
決定性有限オートマトンと同様に五字組みで表す
但し、動作関数σは以下のように表す
Q
σ:Q×Σ→2
形式言語とオートマト
非決定性有限オートマトンとは!?
以下のオートマトンを五字組みで表すと・・・
a
a
r
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンとは!?
Q  {r , s, t}
  {a, b}
Q
 :Q  2
 (r , a)  {r , s},  (r , b)  {r},
 ( s, a)  {t},  ( s, b)   ,
 (t , a)   ,
 (t , b)  
q0  r
F  {t}
形式言語とオートマト
a
a
r
b
s
a
t
非決定性有限オートマトンと
は!?
動作関数の読み方は・・・
 :Q  2
 (r , a)  {r , s},  (r , b)  {r},
 ( s, a)  {t},  ( s, b)   ,
 (t , a)   ,
 (t , b)  
Q
r
a
a
s
b
状態がrで入力記号がaである時は、
rとsどちらに遷移しても良い
形式言語とオートマト
a
t
非決定性有限オートマトンとは!?
動作関数の読み方は・・・
 : Q    2Q
 (r , a)  {r , s},  (r , b)  {r},
 ( s, a)  {t},  ( s, b)   ,
 (t , a)   ,
 (t , b)  
a
a
r
b
状態がtで入力記号がaである時は、
遷移先がないという事
形式言語とオートマト
s
a
t
非決定性有限オートマトンとは!?
この非決定性FSAにbaaを入力する
a
a
r
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンとは!?
この非決定性FSAにbaaを入力する
a
b
a
r
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンと
は!?
この非決定性FSAにbaaを入力する
a
a
ar
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンと
は!?
この非決定性FSAにbaaを入力する
a
a
ar
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンと
は!?
状態r
状態rの
の時、
時、
aaが
されると
が入力
入力
されると
この非決定性FSAに
baa
を入力する
2種の
の遷移
遷移がある
がある
a2種
a
ar
b
形式言語とオートマト
as
a
t
どちらに遷移しても良い
非決定性有限オートマトンと
は!?
baaを入力すると、三種類の遷移がある。
a
a
r
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンと
は!?
baaを入力すると、三種類の遷移がある。
( r , baa ) ( r , aa ) ( r , a ) ( r ,  )
M
M
M
( r , baa ) ( r , aa ) ( r , a ) ( s,  )
M
M
M
( r , baa ) ( r , aa ) ( s, a ) (t ,  )
M
M
M
b ,a
受理状態であるtで遷移が終わって
いるので、baaは受理される
形式言語とオートマト
r
a
s
a
t
非決定性有限オートマトンと
は!?
この非決定性FSAにaabを入力する
a
a
r
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンと
は!?
この非決定性FSAにaabを入力する
a
a
a
r
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンとは!?
この非決定性FSAにaabを入力する
a
a
ar
b
形式言語とオートマト
s
a
t
非決定性有限オートマトンとは!?
この非決定性FSAにaabを入力する
a
a
br
b
形式言語とオートマト
s
a
t
入力bで遷移できるのは
最終的にこの遷移のみ
お疲れさまでした。
小テストです。
形式言語とオートマト