2015/7/3
今日の予定
離散システム論
オートマトンと形式言語論(2)
• 前回の復習
• 形式言語
• 有限オートマトン
– 決定性有限オートマトン
– 非決定性有限オートマトン
知能システム科学
新田克己
• 正規言語
http://www.ntt.dis.titech.ac.jp/sm/risan/
文法と言語とオートマトンの関係
＊
VT
文法G
a
aab
abccbabccc..
…
aa
aabbaa
ababccbaba
…
bcabababccc
文法、形式言語、オートマトン
文法と言語とオートマトンの関係
＊
VT
文法G
Σ
G1
G2
＊
a
aab
abccbabccc..
…
aa
aabbaa
ababccbaba
…
bcabababccc
VT
オートマトンM
状態集合K
アルファベットΣ
初期状態q0
最終状態の集合F
状態遷移関数δ
。。。
M3
M4
オートマトンM
状態集合K
アルファベットΣ
初期状態q0
最終状態の集合F
状態遷移関数δ
。。。
文法と言語とオートマトンの関係
＊
記号列
非終端記号VN
終端記号VT
生成規則P
初期記号σ
＊
記号列
非終端記号VN
終端記号VT
生成規則P
初期記号σ
前回の復習を兼ねて
Σ
文法G
Σ
＊
記号列
非終端記号VN
終端記号VT
生成規則P
言語
初期記号σ
L(G1)
G1
G2
オートマトンM
状態集合K
a
アルファベットΣ
aab
初期状態q0
abccbabccc..
言語 最終状態の集合F
…
L(M3) 状態遷移関数δ
aa
。。。
aabbaa
M3
ababccbaba
…
M4
bcabababccc
1
2015/7/3
文法の定義（その１）
文法の定義（その２）
• 書き換え規則：α→β
α∈V+，β∈V*， V=VN∪VT
文法G=＜VN，VT，P，σ＞
例 { σ, A, B, C }
VN: 非終端記号の集合
例 { a, b, c }
VT: 終端記号の集合
P: 生成規則（書き換え規則）の集合
例 { σ→A, A→B, B→aB }
σ： 初期記号 σ ∈ VN
導出(derivation)
例 A→aB, AB→aB, A→ε
N→dog, V→read • 非終端記号：自然言語の文法では，品詞を
含む文法用語
• 終端記号：自然言語では単語
文法を用いた言語の定義
• 書き換え規則α→βがある場合，記号列AαB(A, B∈V*）はこの規則によりAβBに書き換えられる．
これを導出といい，
AαB⇒AβB
で表す．
例 CD→a なら ACDB ⇒ AaB
• ⇒* は導出の任意回の繰り返しを意味する．
例 A ⇒ B ⇒ bC ⇒ bc
A ⇒ * bc
• 終端記号からなる記号列wが初期記号から
導出されるとき，wを文(sentence)と言う．
• 言語L(G)：文法Gによって生成される言語
L(G)=｛ｗ｜ｗ∈VT*，σ⇒ * ｗ｝
文法Gにより初期記号σから生成される文の
集合
たとえば
S→NP，VP．
NP→Det，N．
NP→N.
VP→V，NP.
Det→a.
N→I. N→girl.
V→saw. …
ここで，Sが初期記号
文法G
S
NP, VP
N,VP
I,VP
I,V,NP
I,saw,NP
I,saw,Det,N
I,saw,a,N
I,saw,a,girl
S
NP,VP
N,VP
I,VP
I,V,NP
I,saw,NP
I,saw,N
I,saw,I
有限オートマトン、正規文法
{ I, saw,a ,girl} ∈ L(G)
2
2015/7/3
オートマトン
オートマトンの一般的構成
• 言語を計算機上で認識（受理）するための抽
象的機械（モデル）
• 制御部：テープの読み書きヘッド＋状態
• 読み込んだ記号により状態を変化させる．
• 初期状態から開始し,入力記号列をすべて読み込ん
だ後の状態が最終状態なら，入力記号列を認識（受
理）したと言う.
• 入力記号列を受理しないことを棄却するとも言う．
• 逆に,初期状態から最終状態までの過程で記号列を
生成することもできる．
(決定性)有限オートマトン
((deterministic) finite automaton)
• M=＜K, Σ, q0, F, δ＞
•
•
•
•
•
K:状態の有限集合
Σ：アルファベット
q0：初期状態, q0∈K
F:最終状態, F⊂K
δ： 状態遷移関数, δ：K×Σ→K
状態遷移図
• 有限オートマトンと対応する有向グラフ表現
• ノードは状態
• 最終状態は,◎で表現する
状態遷移
受理言語（その１）
• 読み込んだ記号と内部状態の組み合わせで,
次の状態を決定する
• 状態qiで入力aが与えられたとき,状態qjに遷
移することをδ(qi,a)=qjと表現する
• δ＾：K×Σ*→K
１) δ＾(q,ε)=q
２) 任意の記号列w,記号aに対して,
δ＾(q,wa) = δ(δ^(q,w),a)
例： δ＾(q,cba)=δ(δ＾(q,cb),a)
=δ(δ(δ(q,c),b),a)
• 有限オートマトンMと記号列wに対して,
δ^(q0, w) ∈Fなら,wはMに受理される(accepted)
と言う.
3
2015/7/3
受理言語(その２）
• Mの受理言語L(M):
Mが受理する記号列すべての集合
• L(M)={w∈Σ*｜δ＾（q0,w)∈F}
たとえば
• 文字aが任意個並んだ文字列を受理するオー
トマトン
• L(M)=｛ε, a, aa, aaa, …}
• 有限オートマトンの受理言語は,正規言語
(regular language)と呼ばれる.
たとえば
• 名詞句N+ Prep N+を受理するオートマトン
（N:名詞,Prep:前置詞）
{ balls for table tennis } 状態遷移図と
受理される文字列集合の関係
• リンクが2つ直列：文字を2つ連接した文字列
が対応(ab)
• ノード間に2つのリンクが並列：2つの文字の
集合（OR)が対応(a+b)
たとえば
(続き)
• ループがある場合,ループをたどる文字列をx
とすると,その閉包x*が対応
• これら3つによって表現された文字列の集合
を正規言語と言う.
(a+b)c(b(a+b)c)*a
4
2015/7/3
演習問題
1．a(b+c)*aに対応する有限オートマトンの状態
遷移図を書いてみましょう.
2．図の有限オートマトンの受理する言語を説
明してください．
非決定性有限オートマトン
(nondeterministic FA)
• ある状態から同一の入力記号に対して複数
の状態へ遷移可能である場合非決定性オー
トマトンと言う.
• したがって,δの値はKの集合となる。
決定性有限オートマトン δ(q1, a) = q2
非決定性有限オートマトン
δ(q1, a) = q2, δ(q1, a) = q3
(つまり、δ(q1, a) = { q2, q3 } )
たとえば
• 「されたら」という文字列を検出する決定性有
限オートマトン
正しく受理するためには
非決定性有限オートマトン
「さされたら」は受理できるか？ できない
非決定性有限オートマトンと
決定性有限オートマトン
• δの値となる状態の集合を1つの状態と見な
すことで,非決定性オートマトンは決定性オー
トマトンへ変換できることが知られている
• 通常,効率の観点から,非決定性オートマトン
は決定性オートマトンに変換した後,言語の認
識に用いられる.
決定性オートマトンへの変換
（その１）
• 部分集合構成法(subset construction)
• 元のオートマトンM=＜K，Σ，q，F ，δ ＞
• 新しいオートマトンM’=＜K’，Σ，q’，F’ ，δ’ ＞
• M’はKの部分集合を状態とし，必要なもの
のみを用いる
5
2015/7/3
決定性オートマトンへの変換
（その２）
• K’ = 2
たとえば
例: K={q0,q1,q2},
K’={{q0},{q1},{q2},{q0,q1},{q0,q2},
{q1,q2},{q1,q2,q3}}
• q’＝｛q｝
• δ’(X，a)=∪p∈Xδ(p，a)
• F’: Fの状態を含むKの部分集合の全体
εｰ動作を許す
非決定性有限オートマトン
MとM’の状態遷移図
非決定性有限オートマトンM
決定性有限オートマトンM‘
0
{q0,q1}
1
δ(q0,0)=q0,
M=<{q0, q1},{0,1},q0,{q1} ,δ >
δ(q0,0)=q1,
δ(q0,0)={q0,q1}, δ(q0,1)={q1}
δ(q0,1)=q1,
δ(q1,1)=q0,
δ(q1,1)={q0,q1}
δ(q1,1)=q1
M’=<K’,{0,1},{q0},F’ ,δ’ >
K’={{q0},{q1},{q0,q1}}, F’={{q1},{q0,q1}}, δ’({q0},0)={q0,q1}, δ’({q0},1)={q1}
δ’({q1},1)={q0,q1}
δ’({q0,q1},0)={q0,q1}, δ’({q0,q1},1)={q0,q1}
• ε‐動作：空列による状態遷移
• ε‐動作を含むオートマトンは,ε‐動作なしの
オートマトンに変換できる.
1
{q1}
0, 1
ε
変換器(transducer)としての
有限オートマトン
• 状態遷移に伴い文字列Aを出力するようにす
る．すなわち，
δ(qi,a)=qj: A
有限オートマトンと正規言語
• 有限オートマトンから対応する正規言語を，
正規言語から対応する有限オートマトンを
それぞれ求める形式的な方法が存在する．
AAKAAKA ああかあか
6
2015/7/3
正規文法
(regular grammar)
• A → a B A, B ∈ VN a ∈VT
状態Aで入力aが与えられたら状態Bへ遷移
δ(A,a)=B
a
A
B
• A → a A ∈ VN a ∈VT
δ(A,a)=F Fは最終状態
a
A
F
文法と言語とオートマトンの関係
＊
VT
文法G
•
•
•
•
•
•
エレベータの制御,
スイッチング回路,
コンパイラ（語彙解析）,
(Unixなどの)正規表現，
かな漢字変換，
…
問題の表現
＊
記号列
非終端記号VN
終端記号VT
生成規則P
初期記号σ
G1
正規文法
G2
有限オートマトンの応用
Σ
a 正規言語
aab
abccbabccc..
…
aa
aabbaa
ababccbaba
…
bcabababccc
オートマトンM
状態集合K
アルファベットΣ
初期状態q0
最終状態の集合F
状態遷移関数δ
。。。
M3
有限オートマトン
M4
狼と山羊とキャベツの問題
• 狼と山羊とキャベツを持った男が川の左岸に
いる. 小船が１つあるが,男が１つの荷物しか
持って乗れない大きさである. 男は持ち物を
すべて右岸に渡したい.だが,狼と山羊だけが
岸にいると,狼は山羊を食べてしまい,山羊と
キャベツだけが岸に残ると,山羊がキャベツを
食べてしまう. 山羊もキャベツも食べられず
に川を渡るにはどうすればよいだろう.
問題の状態遷移図
• M(男),W(狼),G(山羊),C(キャベツ)とすると,状
態は,たとえば,MG‐WC（ｰの左が左岸,右が右
岸）で書ける.ただし,食べられてしまう状態は
取り除く.
• 状態を変化させるもの（入力)は,男の行動.一
人で（m),狼と(w),山羊と(g),キャベツと(c)渡る.
7
2015/7/3
演習問題
宣教師と人喰い人の問題
１．以下の「宣教師と人喰い人の問題｣の状態遷移図
を書きなさい．
３人の宣教師と３人の人喰い人が川の左岸にいる．
1艘の小船を使って全員が右岸に渡りたいが，小船
には最大2人しか乗れず，左岸，右岸いずれでも人
喰い人の数が宣教師の数より多いと宣教師は人喰
い人に食べられてしまう．全員が安全に右岸に渡る
にはどうすればよいだろう．
M
B
C
問題の表現
ヒント
• ３３１－０００
＝＞MC
• ２２０－１１１
＜＝M
• ３２１－０１０
＝＞CC
• ３００ー０３１
。。。。
演習問題
本日のまとめ
2．非決定性有限オートマトンを決定性オートマ
トンに変換しなさい．
M=<{q0, q1, q2},{0,1},q0,{q2} ,δ >
δ(q0,0)={q0,q1}, δ(q0,1)={q0}
δ(q1,1)={q2}
δ(q0,0)=q0,
δ(q0,0)=q1,
δ(q0,1)=q0,
δ(q1,1)=q2
• 有限オートマトン
– 決定性オートマトン
– 状態遷移図
– 受理言語
– 非決定性オートマトン
– 決定性オートマトンへの変換
• 正規言語
＝有限オートマトンで受理される言語
8
© Copyright 2024 ExpyDoc
