形式言語とオートマトン2008 ー第4日目?ー

Formal languages
and
Automata 2012
ーThe 7th Dayー
Tokyo University of Technology
School of Computer Science
Hiroyuki Kameda
前回までの確認
• 有限オートマトン(FA)
– FAの定義と記述法
テープ上を一方向に動くヘッド
(テープ上の記号を順次読みながら内部状態を遷移)
M = <K, Σ, δ, q0, F> (5つ組)
状態遷移図
様相(configuration)
– FAの種類
決定性FA(DFA)
非決定性FA(ε遷移のあるものとないもの)
– 言語認識能力はどのFAでも同じ。
正規言語(正規表現)を認識
2
有限オートマトンのイメージ(1)
• FAの概観
a1 a2
セル
入力記号
・・・
ai-1 ai
・・・
・・・
an
qk
入力テープ
内部状態
ヘッド
3
有限オートマトンのイメージ(2)
FA = ( K, Σ, δ, q0, F )
ただし、
K : 状態の集合( Kは有限集合)
Σ : 入力アルファベット(Σは有限集合)
δ : 状態遷移関数
δ: K×Σ∋( a, qi ) → qj ∈ K
q0 : 初期状態
F : 最終状態の集合 ( F ⊆ K )
4
有限オートマトンのイメージ(2’)
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
5
有限オートマトンのイメージ(3)
a
r
b
a
s
b
b
t
a
6
前回までの確認(2)
•
正規表現を認識するFAの存在とその構成法
正規表現αが与えられる。
正規表現αに対して、ε-NFA を構成する。
ε-NFA をDFAに書き換える。
DFAを状態数が最も少ない最簡形のDFA
(Min-DFA)に書き換える。
5. Min-DFAをシミュレートするプログラムを作成する。
1.
2.
3.
4.
(注)上記5の説明および、最簡形DFA存在とその求め方を
与えるMyhill-Nerodeの定理の説明はまだしていません。
7
前回までの確認(3)
• Pushudown automaton(PDA)
– スタックの定義
データ構造:
・配列(またはアレイ)
・リスト
・スタック
・キュー など
スタックの構造と動作(pop-up と push-down)
LIFO (Last-In First-Out) 型のメモリ
– PDAの定義と記述法
テープ上を一方向に動くヘッド+スタックメモリ
(テープの記号を順次読み、スタック上の記号を順次
読み書きしながら内部状態を遷移)
M = < K, Σ, Γ,δ, q0, Z0, F > (7つ組)
状態遷移図
様相(configuration)
8
前回までの確認(4)
スタックとPDAのイメージ図
Push down
Pop up
LIFO (Last In First Out)
最後に入れたものが最初に取り出される。
9
PDAのイメージ
10
前回までの確認
• Pushdown automaton (PDA)
– PDAの種類
決定性プッシュダウンオートマトン
Deterministic pushdown automaton (DPDA)
非決定性プッシュダウンオートマトン
Nondeterministic pushdown automaton (NPDA)
– 言語認識能力はNPDAの方が高い。
FAは正規言語(正規表現)を認識
NPDAは文脈自由言語を認識
DPDAよりもNPDAの方が言語認識能力大
(注)“言語”そのものの話は後日お話します。
11
今日の内容
• チューリングマシン (Turing Machine)
12
授業ではこの形式のものを扱います
13
TMの定義
• TM M = < Q, Γ, Σ, δ, q0, B, F > (7つ組)
–
–
–
–
Q:内部状態の集合
Γ:テープ記号の集合
Σ:入力記号の集合 ( Σ⊂ Γ )
δ:状態遷移関数
Q×Γ → Q×Γ×{ L, R }
– q0 :初期状態 ( q0 ∈ Q)
– B:ブランク記号 ( B ∈ Γ – Σ)
– F:最終状態の集合 ( F ⊂ Q )
14
TMのイメージ図
15
TM の例
•
•
•
•
•
例4.1(教科書p.90)
例4.2(教科書p.95)
例4.3(教科書p.96)
例4.4(教科書p.100)
例4.5(教科書p.106)
これらを順次確認していきましょう。
16
例4.1(教科書p.90)
入力文字列
• aa
• aabb
• bbaa
•aaaabbbb
17
様相(Configuration)の導入
• (q0, a1 a2 a3 ・・・ ai-1 ↓ai ai+1・・・ an )
18
例4.2(教科書p.95)
M=<Q,Γ,Σ,δ,q0,B,F>
 Q={ q0, q1, q2, q3, qf }
 Σ={ a, b }
 Γ=Σ∪{a’,b’}∪{¢,$,B}
 δ:
δ(q0,a)=(q1,a’,R)
δ(q0,b’)=(q3,b’,R)
δ(q1,a)=(q1,a,R)
δ(q1,b)=(q2,b’,L)
δ(q1,b’)=(q1,b’,R)
δ(q2,a)=(q2,a,L)
δ(q2,a’)=(q0,a’,R)
δ(q2,b’)=(q2,b’,L)
δ(q3,b’)=(q3,b’,R)
δ(q3,$)=(qf,$,L)
19
例4.3(教科書p.96)
• 言語 { anbnan | n>=1 } を受理するTM
20
例4.3(教科書p.96)
21
例4.4(教科書p.100)
• { ww | w ∈ { a, b }+ } を受理するTM
22
23
例4.5(教科書p.106)
• 2進数の和を計算するTM
24
25
今日はここまで
•
•
•
•
•
少しずつ復習をしてください。
個々のものは決して難しくはありません。
引き続き頑張りましょう。
来週は少し難しいです。
来週は少し演習をやりましょう。
26
今日の設問
• ここまでの話で、分かりにくかったものを、分
かりにくかった順にいくつか挙げてください。
27