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

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