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

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

Download Report