Document

Report
形式言語 と オートマト
第5回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定
形式言語とオートマト
非決定性有限オートマトンとは!?
(前回までの授業)
決定性有限オートマトン
すべての状態ですべての入力に対して、
遷移先が唯一
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種
ar
a
as
a
t
b どちらに遷移しても良い
形式言語とオートマト
非決定性有限オートマトンとは!?
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で遷移できるのは
最終的にこの遷移のみ
非決定性有限オートマトンとは!?
aabを入力すると遷移は一種類
( r , aab )  ( r , ab )  ( r , b)  ( r ,  )
M
M
M
a
受理状態でないrで遷移が終わって
いるので、aabは受理されない
a
r
b
形式言語とオートマト
s
a
t
お疲れさまでした。
小テストです。
形式言語とオートマト

similar documents