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

言語プロセッサ2009
-B(後半)平成20年10月5日（月）
東京工科大学
コンピュータサイエンス学部
亀田弘之
Copyright© 2009 School of Computer Science, Tokyo University of Technology
後半はオートマトンの話
• automaton (複数形は,automata)
敢えて訳せば「自動機械」でしたね。
• 教科書の第４章（字句解析）を理解するのに
不可欠ですので、じっくりと学びましょう。
もっと詳しく学びたい人へ
[1] 米田（監修）：オートマトン・言語理論の基礎，近代科学社
[2] 言語理論とオートマトン，サイエンス社など
2
Copyright© 2009 School of Computer Science, Tokyo University of Technology
オートマトンとは
• オートマトン＝自動機械
(automaton, pl. automata)
• もっと具体的には…
いったいどん
なものなのか
なぁ
3
Copyright© 2009 School of Computer Science, Tokyo University of Technology
まずは有限オートマトンから
• Finite Automaton(FA)
– 何がfinite（有限）か？
＝＞内部状態数が有限
もっと詳しく見ていき
ましょう！
4
Copyright© 2009 School of Computer Science, Tokyo University of Technology
有限オートマトンのイメージ
• FAの概観
a1 a2
・・・
ai-1 ai
・・・
・・・
an
qk
5
Copyright© 2009 School of Computer Science, Tokyo University of Technology
有限オートマトンのイメージ
• FAの概観
a1 a2
セル
入力記号
・・・
ai-1 ai
・・・
・・・
an
qk
入力テープ
内部状態
ヘッド
6
Copyright© 2009 School of Computer Science, Tokyo University of Technology
有限オートマトンのイメージ
• FAの概観
a1 a2
セル
入力記号
・・・
ai-1 ai
・・・
・・・
an
qk
入力テープ
内部状態
ヘッド
7
Copyright© 2009 School of Computer Science, Tokyo University of Technology
• このようなハードウェアをもった自動機械が、
入力記号を読みながら内部状態を変化させ
ていく、といったもの。
• 言葉で表現すると次のようになる。
8
Copyright© 2009 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© 2009 School of Computer Science, Tokyo University of Technology
それでは、具体例をみてみましょう。
10
Copyright© 2009 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© 2009 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© 2009 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© 2009 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 )
14
Copyright© 2009 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© 2009 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© 2009 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© 2009 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© 2009 School of Computer Science, Tokyo University of Technology
つまり
19
Copyright© 2009 School of Computer Science, Tokyo University of Technology
有限オートマトンの例
K = { r, s, t} , Σ= { a, b }入力アルファベット,
q0 = r, F ={ t },
δ ：
状態入力次の状態
r
a
s
r
b
r
s
a
t
s
b
r
t
a
t
t
b
r
20
Copyright© 2009 School of Computer Science, Tokyo University of Technology
このFAを動作させてみましょう
•
入力文字列
1. abaa
2. bababa
3. aabbaabb
21
Copyright© 2009 School of Computer Science, Tokyo University of Technology
以上のFAは決定性FAともいう
• 決定性有限オートマトン
（Deterministic FA; DFA）
？？？
後で、
非決定性オートマトン(Non-deterministic finite automaton; NFA)
が出てきます。
22
Copyright© 2009 School of Computer Science, Tokyo University of Technology
FAの視覚的表記法
• 言葉よりも図の方が分かりやすいこともある。
• 便利なので覚えましょう。簡単です！
よかったぁ
23
Copyright© 2009 School of Computer Science, Tokyo University of Technology
初めに内部状態ありき
s
r
t
24
Copyright© 2009 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
25
Copyright© 2009 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
s
t
26
Copyright© 2009 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
s
t
27
Copyright© 2009 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
t
28
Copyright© 2009 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
b
t
29
Copyright© 2009 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
b
t
a
30
Copyright© 2009 School of Computer Science, Tokyo University of Technology
遷移の条件と行き先を記入
a
r
b
a
s
b
b
t
a
31
Copyright© 2009 School of Computer Science, Tokyo University of Technology
初期状態と最終状態を記入
a
r
b
a
s
b
b
t
a
32
Copyright© 2009 School of Computer Science, Tokyo University of Technology
もう一度動作させてみよう
•
入力文字列
1. abaa
2. bababa
3. aabbaabb
33
Copyright© 2009 School of Computer Science, Tokyo University of Technology
練習問題
34
Copyright© 2009 School of Computer Science, Tokyo University of Technology
以上のFAは決定性FAという
• 決定性有限オートマトン
（Deterministic FA; DFA）
• 次に、非決定性有限オートマトン
（Non-deterministic Finite Automaton;
NFA）
35
Copyright© 2009 School of Computer Science, Tokyo University of Technology
非決定性有限オートマトンの定義
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
K×Σ∋( a, qi ) → (qk, ql,…,qm)∈ 2K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
36
Copyright© 2009 School of Computer Science, Tokyo University of Technology
例
37
Copyright© 2009 School of Computer Science, Tokyo University of Technology
ε非決定性有限オートマトン
• 空動作を許容する非決定性有限オートマトン
(non-deterministic FA with ε; ε-NFA)
38
Copyright© 2009 School of Computer Science, Tokyo University of Technology
ε非決定性有限オートマトンの定義
FA = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
K×(Σ∪{ε})∋ → 2K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
39
Copyright© 2009 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 } 最終状態の集合
40
Copyright© 2009 School of Computer Science, Tokyo University of Technology
δ：状態遷移関数
• δ(p,ε)＝{ q, r }
• δ(q,0)＝{ q }
• δ(r,1)＝{ r },
41
Copyright© 2009 School of Computer Science, Tokyo University of Technology
状態遷移図にすると…
(自分で書いてみよう)
検討：このオートマトンはどんな文字列を
受理するのだろうか？
42
Copyright© 2009 School of Computer Science, Tokyo University of Technology
練習問題
43
Copyright© 2009 School of Computer Science, Tokyo University of Technology
注意事項
• DFA －＞ NFA －＞ ε-NFA
「条件を順次緩めた」
ということは、より多くの文字列を受理できる？
つまり、より大きな言語・より多様な言語を受理す
ることができる？
44
Copyright© 2009 School of Computer Science, Tokyo University of Technology
いいえ
違います
本当なの？！
あら、残念…
45
Copyright© 2009 School of Computer Science, Tokyo University of Technology
• FA, NFA, ε-NFA は同等の能力
（言語の生成・受理の能力として）
• FAの方が簡潔だよね！
• ε-NFAをFAに、それも状態数が最小のFAに
変換する方法について学ぼう！
（教科書のp.61あたりに書いてあります。）
• 次回は、まず、p.29あたりからはじめます。
46
Copyright© 2009 School of Computer Science, Tokyo University of Technology
次の話題
Backus Naur Form (構文要素の記述)
構文図式(構文の視覚的表示)
文法（構文の形式的記述）
構文木（構文構造の視覚的表示）
正規表現＝FA
ε-NFA -> NFA -> FA -> 状態数最少FA
FAのプログラムへの変換
LEX（プログラムの自動生成）
47
Copyright© 2009 School of Computer Science, Tokyo University of Technology
付録
• オートマトンの動作イメージ
– 動作の初めの部分のみ
– 興味のある人は続きを自分で作ってみてください。
48
Copyright© 2009 School of Computer Science, Tokyo University of Technology
有限オートマトンの動作
• FAの概観
a1 a2
・・・
ai-1 ai
・・・
・・・
an
qk
49
Copyright© 2009 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
50
Copyright© 2009 School of Computer Science, Tokyo University of Technology
続きは自由課題です。
51
Copyright© 2009 School of Computer Science, Tokyo University of Technology
ここまでのまとめ
• 文字列認識装置としてのオートマトンを復讐
した。
52
Copyright© 2009 School of Computer Science, Tokyo University of Technology
とうことは、
• #include <stdio.h>
int main( ) {
int x;
x = 10;
x += 5;
printf(“xの値は=%d“, x);
}
このようなものを認識できるオートマト
ンが作れるってこと？
53
Copyright© 2009 School of Computer Science, Tokyo University of Technology

Download Report