スライド 1

形式言語とオートマト
第2回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
復習
復
形式言語とオートマト
習
復習
機械（オートマトン）による仕事
一定の規則を与えられ，
その通りに作業する
単純な仕事：単純な規則(例:偶奇判別)
複雑さのレベルを上げると
できる仕事のレベルも上がる
複雑な仕事：複雑な規則(例:計算，言語)
形式言語とオートマト
復習
単純な仕事は単純な仕掛けで
２状態だけで判断できるのは
↑
{偶,奇},
形式言語とオートマト
↓
{点,滅},
{合,否}
復習
単純な仕事は単純な仕掛けで
２状態を二つ使えば、4つを区別できる
↑
↑
↓
↓
{（↑↑）,（↑↓）,(↓↑),（↓↓）}の４つ
形式言語とオートマト
復習
単純な仕事は単純な仕掛けで
８
２状態を３つ使えば、、
{（↑↑↑）,（↑↑↓）,(↑↓↑),（↑↓↓）,
（↓↑↑）,（↓↑↓）,(↓↓↑),（↓↓↓）}
８つを区別できる
形式言語とオートマト
復習
単純な仕事は単純な仕掛けで
８
２状態をN個使えば、、
{（↑↑…↑↑）, （↑↑…↑↓）,（↑↑…↓↑）,
（↑↑…↓↓）,…,(↓↓…↑↓),（↓↓…↓↓）}
2N個を区別できる
形式言語とオートマト
オートマトンの状態遷移図表現
状態遷移図で表す
有限オートマトン
形式言語とオートマト
オートマトンの状態遷移図表現
言語理解の原理： aとbからなる文字列
規則： bで読み終われば受理する（例abbb,ab）
条件を満す時→「受」で文字列を読み終わる
条件を満さない時→「拒」で文字列を読み終わる
a
b
b
拒
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば，aaを入力してみる
a
a
b
b
拒
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば，aaを入力してみる
a
b
b
拒
a
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば，aｂを入力してみる
a
a
b
b
拒
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば，aｂを入力してみる
a
b
b拒
形式言語とオートマト
b
1文字読むたびに
受
a 機械の状態が変化
有限オートマトンの５字組み表
現
5字組みで表す
有限オートマト
ン
形式言語とオートマト
有限オートマトンの５字組み表
現
5字組み表現
M= <Ｑ，Σ，δ，q0，Ｆ>
Ｑ⇒状態の有限集合
Σ ⇒入力記号の有限集合
δ ⇒動作関数(δ:Ｑ×Σ→Ｑ)
q0⇒初期状態(q0∈ Ｑ)
F ⇒受理状態の集合
形式言語とオートマト
有限オートマトンの５字組み表
現
状態の有限集合
Ｑ = {q1 , q2}
状態の集合
a
b
q１
b
a
形式言語とオートマト
q2
有限オートマトンの５字組み表
現
入力記号の有限集合
Σ = {a , b}
a
b
q１
b
a
形式言語とオートマト
q2
有限オートマトンの５字組み表
現
動作関数(δ:Ｑ×Σ→Ｑ)
δ (q1 , a) = q1
δ (q1 , b) = q2
δ (q2 , a) = q1
δ (q2 , b) = q2
a
b
q１
δ (q1,b) = q2
b
q2
a
機械が状態q1にいるときに入力bを読むと状態q2に移る
形式言語とオートマト
有限オートマトンの５字組み表
現
初期状態(q0∈ Ｑ)
q0 = q 1
a
b
b
q１
q2
a
二重矢印：どの状態が初期状態かを指定する
形式言語とオートマト
有限オートマトンの５字組み表
現
受理状態の集合
Ｆ = {q２}
a
b
b
q１
q2
a
二重丸：どの状態が終了状態かを指定する
形式言語とオートマト
有限オートマトンの５字組み表
現
5字組み表現
M= <Ｑ，Σ，δ，q0，Ｆ>
Ｑ = {q1 , q2}
Σ = {a , b}
δ ：Ｑ×Σ→Ｑ
δ (q1 , a) = q1
δ (q1 , b) = q2
δ (q2 , a) = q1
δ (q2 , b) = q2
q0 = q 1
Ｆ = {q2}
形式言語とオートマト
a
q１
b
q2
a
状態遷移図と
5字組みが等価
b
有限オートマトン
（Finite State Automata：
FSA）
の
5字組による表示
形式言語とオートマト
有限オートマトンの５字組み表
現
問題：下右図の有限オートマトンを5字組みで表せ
b
r
a
b
s
a
b
t
a
FSA： M = <Q, Σ, δ，q, F> の５字組
形式言語とオートマト
有限オートマトン
（Finite State Automata：
FSA）
FSA： M = <Q, Σ, d, q, F> の５字組
・ 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)を使って調べる
形式言語とオートマト
abbaを与えたときの一
連の動作を下記のように
簡潔に表す
(r,abba)
M
(s,bba)
M
(r,ba)
様相
形式言語とオートマト
M
(r,a)
M
(s,ε)
様相の定義：
(オートマトンの状態，未読の入力）
(r,abba)
M
(s,bba)
M
(r,ba)
様相
形式言語とオートマト
M
(r,a)
M
(s,ε)
最初と最後の様相だけに
関心があるときは
(r,abba)
形式言語とオートマト
＊
M
(s,ε)
オートマトンの動作に従い、状態
が変化し，未読入力が減ってゆく
(r,abba)
M
(s,bba)
形式言語とオートマト
M
(r,ba)
M
(r,a)
M
(s,ε)
最後に（終状態, 空列）となった
ら受理、そうでなければ受理しない
(r,abba)
M
(s,bba)
M
(r,ba)
M
(r,a)
M
(s,ε)
受理状態でないで終了
→拒否
形式言語とオートマト
先の図と同じ5字組みによる表示したMに
aaaaを入力してみる
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,aaaa)
(t,aa)
M
M
(s,aaa)
(t,a)
受理状態で終了
→受理
M
M
(t,ε)
形式言語とオートマト
非決定性有限オートマトンとは!?
決定性有限オートマトン
すべての状態ですべての入力に対して、
遷移先が唯一
a
形式言語とオートマト
非決定性有限オートマトンとは!?
非決定性有限オートマトン
一つの入力に対し、遷移先が唯一でない
a
a
形式言語とオートマト
非決定性有限オートマトンとは!?
非決定性有限オートマトン
決定性有限オートマトンと同様に五字組みで表す
但し、動作関数σは以下のように表す
Ｑ
σ:Ｑ×Σ→２
形式言語とオートマト
非決定性FAの様相(=時点表示)
状態rでa を入力すると遷移は２種類
(r,aab)
M
(r,ab)
M
(r,b)
M
(r,ab)
M
(s,b)
受理状態でないｒで入力が尽きるか、
状態ｓでbを読めない、のどちらにし
てもaabは受理されない
形式言語とオートマト
M
(r,ε)
a
a
r
b
s
a
t
非決定性有限オートマトンとは!?
以下のオートマトンを五字組みで表すと・・・
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
非決定性有限オートマトンと
は!?
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
受理状態であるtで遷移が終わって
いるので、baaは受理される
形式言語とオートマト
○
M
r
a
s
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で遷移できるのは
最終的にこの遷移のみ
お疲れさまでした。
小テストです。
形式言語とオートマト

Download Report