言語プロセッサ2005 -No.3-

形式言語とオートマトン2011
-No.2平成23年4月26日（火）
東京工科大学
コンピュータサイエンス学部
亀田弘之
Copyright© 2011 School of Computer Science, Tokyo University of Technology
今日は有限オートマトンの話
• automaton (複数形は,automata)
敢えて訳せば「自動機械」でしたね。
• 内容は教科書の第２章です。
• 「計算の原理」を理解するための基礎ですの
で、じっくりと学びましょう。
もっと詳しく学びたい人へ
[1] 言語理論とオートマトン，ホップクロフト・ウルマン，サイエンス社
[2] 形式言語の理論，西野・石坂，丸善など
2
Copyright© 2011 School of Computer Science, Tokyo University of Technology
オートマトンとは
• オートマトン＝自動機械
(automaton, pl. automata)
• もっと具体的には…
いったいどん
なものなのか
なぁ
3
Copyright© 2011 School of Computer Science, Tokyo University of Technology
まずは有限オートマトンから
• Finite Automaton(FA)
– 何がfinite（有限）か？
＝＞内部状態数が有限
もっと詳しく見ていき
ましょう！
4
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンのイメージ
• FAの概観
a1 a2
・・・
ai-1 ai
・・・
・・・
an
qk
5
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンのイメージ
• FAの概観
a1 a2
セル
入力記号
・・・
ai-1 ai
・・・
・・・
an
qk
入力テープ
内部状態
ヘッド
6
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンのイメージ
• FAの概観
a1 a2
セル
入力記号
・・・
ai-1 ai
・・・
・・・
an
qk
入力テープ
内部状態
ヘッド
7
Copyright© 2011 School of Computer Science, Tokyo University of Technology
• このようなハードウェアをもった自動機械が、
入力記号を読みながら内部状態を変化させ
ていく、といったもの。
• 言葉で厳密に表現すると次のようになる。
8
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの定義
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
δ： K×Σ∋( qi , a ) → qj ∈ K
q0 ：初期状態
なるほど
そうです
か
F ：最終状態の集合 ( F ⊆ K )
でも、よくわからないなぁ
9
Copyright© 2011 School of Computer Science, Tokyo University of Technology
それでは、具体例をみてみましょう。
10
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
δ： K×Σ∋( qi , a ) → qj ∈ K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
11
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
FA = ( K, Σ, δ, q0, F )
ただし、
K ： { r, s, t } 状態の集合
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
δ： K×Σ∋( a, qi ) → qj ∈ K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
12
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
FA = ( K, Σ, δ, q0, F )
ただし、
K ： { r, s, t } 状態の集合
Σ ： { a, b }入力アルファベット
δ ：状態遷移関数
δ： K×Σ∋( a, qi ) → qj ∈ K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
13
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
FA = ( K, Σ, δ, q0, F )
ただし、
K ： { r, s, t } 状態の集合
Σ ： { a, b }入力アルファベット
δ ：状態遷移関数
δ： K×Σ∋( qi , a) → qj ∈ K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
14
Copyright© 2011 School of Computer Science, Tokyo University of Technology
δ
：状態遷移関数
δ（r, a）＝s, δ（r, b）＝r,
δ（s, a）＝t, δ（s, b）＝r,
δ（t, a）＝t, δ（t, b）＝r
状態
入力次の状態
r
a
s
r
b
r
s
a
t
s
b
r
t
a
t
t
b
r
15
Copyright© 2011 School of Computer Science, Tokyo University of Technology
δ
：状態遷移関数
δ（r, a）＝s, δ（r, b）＝r,
δ（s, a）＝t, δ（s, b）＝r,
δ（t, a）＝t, δ（t, b）＝r
内部入力
状態
外部入力
入力次の状態
r
a
s
r
b
r
s
a
t
s
b
r
t
a
t
t
b
r
16
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
FA = ( K, Σ, δ, q0, F )
ただし、
K ： { r, s, t } 状態の集合
Σ ： { a, b }入力アルファベット
δ ：状態遷移関数
δ： K×Σ∋( a, qi ) → qj ∈ K
q0 ： r 初期状態
F ：最終状態の集合 ( F ⊆ K )
17
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
FA = ( K, Σ, δ, q0, F )
ただし、
K ： { r, s, t } 状態の集合
Σ ： { a, b }入力アルファベット
δ ：状態遷移関数
δ： K×Σ∋( a, qi ) → qj ∈ K
q0 ： r 初期状態
F ： { t } 最終状態の集合 ( F ⊆ K )
18
Copyright© 2011 School of Computer Science, Tokyo University of Technology
つまり
19
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
K = { r, s, t} ,
q0 = r,
δ ：
状態
r
r
s
s
t
t
Σ= { a, b },
F
={ t },
入力次の状態
a
s
b
r
a
t
b
r
a
t
b
r
20
Copyright© 2011 School of Computer Science, Tokyo University of Technology
このFAを動作させてみましょう
•
入力文字列
1. abaa
2. bababa
3. aabbaabb
21
Copyright© 2011 School of Computer Science, Tokyo University of Technology
以上のFAは決定性FAともいう
• 決定性有限オートマトン
（Deterministic FA; DFA）
？？？
この後で、
非決定性オートマトン(Non-deterministic finite automaton; NFA)
が出てきます。
22
Copyright© 2011 School of Computer Science, Tokyo University of Technology
FAの視覚的表記法
• 言葉よりも図の方が分かりやすいこともある。
• 便利なので覚えましょう。簡単です！
よかったぁ
23
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの定義
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
δ： K×Σ∋( qi , a ) → qj ∈ K
理論的形式
q0 ：初期状態
的定義だとこ
うなる
F ：最終状態の集合 ( F ⊆ K )
24
Copyright© 2011 School of Computer Science, Tokyo University of Technology
これを視覚的に表記すると…
25
Copyright© 2011 School of Computer Science, Tokyo University of Technology
初めに内部状態ありき
s
r
t
26
Copyright© 2011 School of Computer Science, Tokyo University of Technology
δ：状態遷移関数をみながら…
δ（r, a）＝s, δ（r, b）＝r,
δ（s, a）＝t, δ（s, b）＝r,
δ（t, a）＝t, δ（t, b）＝r
状態
入力次の状態
r
a
s
r
b
r
s
a
t
s
b
r
t
a
t
t
b
r
27
Copyright© 2011 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
s
t
28
Copyright© 2011 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
s
t
29
Copyright© 2011 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
t
30
Copyright© 2011 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
b
t
31
Copyright© 2011 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
b
t
a
32
Copyright© 2011 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
b
b
t
a
33
Copyright© 2011 School of Computer Science, Tokyo University of Technology
初期状態と最終状態を記入
a
r
b
a
s
b
b
t
a
34
Copyright© 2011 School of Computer Science, Tokyo University of Technology
もう一度動作させてみよう
•
入力文字列
1.
2.
3.
4.
abaa
bababa
aabbaabb
bbaabbaa
35
Copyright© 2011 School of Computer Science, Tokyo University of Technology
練習問題
36
Copyright© 2011 School of Computer Science, Tokyo University of Technology
問題1
• 本パワーポイントの２０ページのオートマトン
に対して、入力文字列 abbaa を与えた場合
の一連の動作を、教科書34ページ下に書い
てある記号 |- を用いて記述せよ。
37
Copyright© 2011 School of Computer Science, Tokyo University of Technology
問題２
• M = ( K, Σ, δ, q0, F ) の各記号は何か。
– K：＿＿＿＿＿＿＿＿
– Σ：＿＿＿＿＿＿＿＿
– δ：＿＿＿＿＿＿＿＿
– q0：＿＿＿＿＿＿＿＿
– F：＿＿＿＿＿＿＿＿
38
Copyright© 2011 School of Computer Science, Tokyo University of Technology
問題３
• M1 = ( K, Σ, δ, q0, F ) を遷移図表示せよ。
ただし、
– K = { q0, q1, q2, q3 }
– Σ = { 0, 1 }
– δ: δ(q0,0)=q2, δ(q0,1)=q1, δ(q1,0)=q3,
δ(q1,1)=q0, δ(q2,0)=q0, δ(q2,1)=q3,
δ(q3,0)=q1, δ(q3,1)=q2
– q0
– F = { q0 }
39
Copyright© 2011 School of Computer Science, Tokyo University of Technology
問題４
• 問題３で定義されるオートマトンM1が受理す
る文字列および受理しない（拒否する）文字
列をそれぞれ５つずつ例示しなさい。
（注）受理する：accept
拒絶する：reject
これらは専門用語です。
40
Copyright© 2011 School of Computer Science, Tokyo University of Technology
以上のFAは決定性FAという
• 決定性有限オートマトン
（Deterministic FA; DFA）
• 次に、非決定性有限オートマトン
（Non-deterministic Finite Automaton; NFA）
41
Copyright© 2011 School of Computer Science, Tokyo University of Technology
非決定性有限オートマトンの定義
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
K×Σ∋( qi, a ) → (qk, ql,…,qm)∈ 2K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
42
Copyright© 2011 School of Computer Science, Tokyo University of Technology
例
• （教科書p.40 例2.4）
43
Copyright© 2011 School of Computer Science, Tokyo University of Technology
ε非決定性有限オートマトン
• 空動作を許容する非決定性有限オートマトン
(non-deterministic FA with ε; ε-NFA)
44
Copyright© 2011 School of Computer Science, Tokyo University of Technology
ε非決定性有限オートマトンの定義
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
K×(Σ∪{ε})∋ → 2K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
45
Copyright© 2011 School of Computer Science, Tokyo University of Technology
ε-NFAの例
FA = ( K, Σ, δ, q0, F )
ただし、
K ： { p, q, r} 状態の集合
Σ ： { 0, 1 }入力アルファベット
δ ：状態遷移関数
δ： K×(Σ∪{ε})∋ → 2K
q0 ： p 初期状態
F ： { q, r } 最終状態の集合
46
Copyright© 2011 School of Computer Science, Tokyo University of Technology
δ：状態遷移関数
• δ(p,ε)＝{ q, r }
• δ(q,0)＝{ q }
• δ(r,1)＝{ r },
47
Copyright© 2011 School of Computer Science, Tokyo University of Technology
状態遷移図にすると…
(自分で書いてみよう)
検討：このオートマトンはどんな文字列を
受理するのだろうか？
48
Copyright© 2011 School of Computer Science, Tokyo University of Technology
練習問題
• (今回はなし。次回授業でやりましょう。)
49
Copyright© 2011 School of Computer Science, Tokyo University of Technology
注意事項
• DFA －＞ NFA －＞ ε-NFA
「条件を順次緩めた」
ということは、より多くの文字列を受理できる？
つまり、より大きな言語・より多様な言語を
受理することができる？
50
Copyright© 2011 School of Computer Science, Tokyo University of Technology
No!
本当なの？！
でも、なぜ？
51
Copyright© 2011 School of Computer Science, Tokyo University of Technology
• DFA, NFA, ε-NFA は同等の能力
（言語の生成・受理の能力として）
• DFAの方が簡潔だよね！
• ε-NFAをDFAに、それも状態数が最小のFAに変換
する方法について学ぼう！
（教科書のp.51あたりに書いてあります。）
• 次回は、復習をしながら正規表現との関係を話しま
す。
52
Copyright© 2011 School of Computer Science, Tokyo University of Technology
宿題（提出不要）
• 教科書の例題等を確認しておくこと。
– 例2.1
– 問2.1
– 問2.2
– 問2.3
– 例2.4
– 例2.5
– 問2.5
53
Copyright© 2011 School of Computer Science, Tokyo University of Technology
付録
• オートマトンの動作イメージ
– 動作の初めの部分のみ
– 興味のある人は続きを自分で作ってみてください。
54
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの動作
• FAの概観
a1 a2
・・・
ai-1 ai
・・・
・・・
an
qk
55
Copyright© 2011 School of Computer Science, Tokyo University of Technology
有限オートマトンの動作
• FAの概観
a
b
r s
a
a
q
X
q’
r
a
s
r
b
r
s
a
t
s
b
r
t
a
t
t
b
r
56
Copyright© 2011 School of Computer Science, Tokyo University of Technology

Download Report