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

形式言語とオートマトン2012
ー第6日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
前回までの確認
• 有限オートマトン(FA)
– FAの定義と記述法
テープ上を一方向に動くヘッド
（テープ上の記号を読みながら、内部状態を変えていく）
M = <K, Σ, δ, q0, F>
状態遷移図
– FAの種類
決定性FA（DFA）
非決定性FA（ε遷移のあるものとないもの）
– 言語認識能力はどのFAでも同じ。
正規言語（正規表現）を認識可能。
2
前回までの確認（２）
•
正規表現を認識するFAの存在とその構成法
1.
2.
3.
4.
5.
正規表現αが与えられる。
正規表現αに対して、ε-NFA を構成する。
ε-NFA をDFAに書き換える。
DFAを状態数最少のDFAに書き換える。
Min-DFAをシミュレートするプログラムを作成する。
3
確認問題集
• （少しずつこなしていってください。）
4
確認問題１
• （オートマトンの定義）
次の状態遷移図で与えられるオートマトンを、
M=＜K,Σ,δ,q0, F＞の５つ組で記述しなさい。
a
p
b
a
q
a
b
r
b
5
確認問題
•
前問のオートマトンの動作のトレース
– 次の文字列のうち、前問のオートマトンMが
受理するのはどれとどれですか？
①
②
③
④
aabba
bababbb
aaaa
bbba
6
確認問題
• 下図のε-NFAをDFAに書き換えなさい。
４ b
a
１
ε
ε
２
３
５ c
b
b
ε
６
a
７
８
c
ε
7
確認問題
• DFAからmin-DFAを求める手順について
述べなさい。
（理論的根拠は、後日お話します。MyhillNerodeの定理がポイントになりす。）
8
確認問題
•
（正規表現を受理するmin-DFAを求める）
次の正規表現を受理するmin-DFAを求めよ。
1. (ab|bc)*a(b|c)
2. (a|b|ε)(ab|b)*bc
3. (a|b)*a(a|b)
9
さて、…
10
今日の話題
1. FAの様相(configuration)
(第2章の補足)
2. プッシュダウンオートマトン
（pushdown automaton）
（第3章の話）
11
FAの様相
• FAの動作の様子・状況を様相(configuration)
という。
• 動作開始時の様相を特に、初期様相という。
12
様相の表現
入力文字列
入力文字列の末尾
13
様相表現の例
• （具体例で理解しよう）
教科書p.36 問2.1
14
FA M = <K, Σ, δ, q0, F>
0
1
q
0
1
p
0
r
1
15
FA M = <K, Σ, δ, q0, F>
0
1
q
0
1
p
0
r
1
様相(p, 11010) |- (q,1010) |- (q,010) |- (q,10) |- (q, 0) |- (q, ε)
(p,11010) |*- (q,ε) <= Mは入力文字列 11010 を受理
16
• 様相(configuration)という用語は、本を読ん
でいると時々出てきます。
• オートマトンの動作状況を表現する単なる
１つの方法にすぎません。
でも、便利ですよね。
17
自主練習
教科書p.58の【演習問題】にチャレンジしてくだ
さい。
18
ここから新しい話し
• （第３章に入ります）
Let’s get down
to today’s topics.
19
プッシュダウンオートマトン
• 有限オートマトンにプッシュダウンスタックメモリ
を追加装備したもの。
• Pushdown automaton (PDA)
20
プッシュダウンスタック
• 歴史的view:
– 初期の頃：プッシュダウン型スタックメモリ
（特殊なハードウェアと考えていた）
– 現在：「スタック」は基本的なデータ構造の１つと
考えられている。プッシュダウンスタックとは言わ
ず、スタックと呼ぶことが多い。
データ構造：
・配列（またはアレイ）
・リスト
続きは「データ構造とアルゴリズム」で。
・スタック
・キューなど
21
プッシュダウンスタックのイメージ
Push down
Pop up
LIFO (Last In First Out)
最後に入れたものが最初に取り出される。
22
PDAの種類
• 決定性プッシュダウンオートマトン
Deterministic pushdown automaton (DPDA)
• 非決定性プッシュダウンオートマトン
Nondeterministic pushdown automaton (NPDA)
23
DPDA M の定義
• M = <K, Σ, Γ, δ, q0, Z0, F>
– K:内部状態の集合（#K < ∞）
– Σ：入力アルファベット（#Σ < ∞）
– Γ：プッシュダウンアルファベット（#Γ < ∞）
– δ：状態遷移関数
K×(Σ∪{ε})×Γ → K×Γ*
– q0：初期状態 (q0 ∈K )
– Z0：ボトムマーカ ( Z0∈Γ)
– F：最終状態 ( F ⊂ K )
24
DPDA M の定義
• M = <K, Σ, Γ, δ, q0, Z0, F>
– K:内部状態の集合（#K < ∞）
– Σ：入力アルファベット（#Σ < ∞）
– Γ：プッシュダウンアルファベット（#Γ < ∞）
– δ：状態遷移関数
K×(Σ∪{ε})×Γ → K×Γ*
– q0：初期状態 (q0 ∈K )
– Z0：ボトムマーカ ( Z0∈Γ)
– F：最終状態 ( F ⊂ K )
25
ハードウェア構成でのイメージ
26
DFA と DPDA
類似点と相違点
類似点：
相違点：
・入力テープ
・プッシュダウンスタックメモリ
（左から右へ読み込むだけ）
・ヘッドとその内部状態
27
研究
ハードウェア構成でのイメージ
なぜ、プッシュダウンスタック？
28
研究テーマ
内部処理
装置
記憶装置
29
難しいことはさておいて…
• (例を見てみましょう)
教科書p.68例3.1
30
DPDA M の例
• M = <K, Σ, Γ, δ, q0, Z0, F>
– K内部状態の集合 = { q0, q1, q2 } （#K < ∞）
– Σ入力アルファベット = { a, b } （#Σ < ∞）
– Γプッシュダウンアルファベット = { A, Z0 }（#Γ< ∞）
– δ：状態遷移関数
K×(Σ∪{ε})×Γ → K×Γ*
– q0 初期状態 = q0 (q0 ∈K )
– Z0：ボトムマーカ ( Z0∈Γ)
– F：最終状態 F = { q2 } ⊂ K
31
δ：状態遷移関数
K×(Σ∪{ε})×Γ
K×Γ*
δ( q0, a, Z0 )
( q0, AZ0 )
δ( q0, a, A )
( q0, AA )
δ( q0, b, A )
( q 1, ε )
δ( q1, b, A )
( q 1, ε )
δ( q1, ε, Z0 )
( q2, Z0 )
32
DPDA M の例
• M=
<K,Σ,Γ,δ,q0,Z0, F>
–
–
–
–
–
–
–
K = { q0, q1, q2 }
Σ = { a, b }
Γ = { A, Z0 }
δ：状態遷移関数
q0 ：初期期状態
Z0：ボトムマーカ
F = { q2 }⊂ K
K×(Σ∪{ε})×Γ
K×Γ*
δ( q0, a, Z0 )
( q0, AZ0 )
δ( q0, a, A )
( q0, AA )
δ( q0, b, A )
( q 1, ε )
δ( q1, b, A )
( q 1, ε )
δ( q1, ε, Z0 )
( q2, Z0 )
33
動作のトレース
• (q0, aaabbb, Z0)
|- (q0, aabbb, AZ0)
|- (q0, abbb, AAZ0)
|- (q0, bbb, AAAZ0)
|- (q1, bb, AAZ0)
|- (q1, b, AZ0)
|- (q1, ε, Z0)
|- (q2, ε, Z0) 受理
• |- (q0, aab, Z0)
|- (q0, ab, AZ0)
|- (q0, b, AAZ0)
|- (q0, ε, AZ0) 拒否
K×(Σ∪{ε})×Γ
K×Γ*
δ( q0, a, Z0 )
( q0, AZ0 )
δ( q0, a, A )
( q0, AA )
δ( q0, b, A )
( q 1, ε )
δ( q1, b, A )
( q 1, ε )
δ( q1, ε, Z0 )
( q2, Z0 )
34
状態遷移図
35
動作のトレース
• (q0, aaabbb, Z0)
|- (q0, aabbb, AZ0)
|- (q0, abbb, AAZ0)
|- (q0, bbb, AAAZ0)
|- (q1, bb, AAZ0)
|- (q1, b, AZ0)
|- (q1, ε, Z0)
|- (q2, ε, Z0) 受理
• |- (q0, aab, Z0)
|- (q0, ab, AZ0)
|- (q0, b, AAZ0)
|- (q１, ε, AZ0) 拒否
自分で確認しよう
K×(Σ∪{ε})×Γ
K×Γ*
δ( q0, a, Z0 )
( q0, AZ0 )
δ( q0, a, A )
( q0, AA )
δ( q0, b, A )
( q1, ε )
δ( q1, b, A )
( q1, ε )
δ( q1, ε, Z0 )
( q2, Z0 )
36
練習
• 教科書のp.71 問題3.1の DPDA の動作を
いろいろな入力に対して調べてみよう。
37
非決定性プッシュダウンオートマトン
• DPDAでの状態遷移関数部分が
１対多の写像になる。
38
DPDA M の定義（再）
• M = <K, Σ, Γ, δ, q0, Z0, F>
– K:内部状態の集合（#K < ∞）
– Σ：入力アルファベット（#Σ < ∞）
– Γ：プッシュダウンアルファベット（#Γ < ∞）
– δ：状態遷移関数
K×(Σ∪{ε})×Γ → K×Γ*
– q0：初期状態 (q0 ∈K )
– Z0：ボトムマーカ ( Z0∈Γ)
– F：最終状態 ( F ⊂ K )
39
NPDA M の定義（再）
• M = <K, Σ, Γ, δ, q0, Z0, F>
– K:内部状態の集合（#K < ∞）
– Σ：入力アルファベット（#Σ < ∞）
– Γ：プッシュダウンアルファベット（#Γ < ∞）
– δ：状態遷移関数
K×(Σ∪{ε})×Γ → ２K×Γ*
– q0：初期状態 (q0 ∈K )
– Z0：ボトムマーカ ( Z0∈Γ)
– F：最終状態 ( F ⊂ K )
40
DPDA M の例
• M = <K, Σ, Γ, δ, q0, Z0, F>
（教科書p.73の例3.2）
41
NPDA M の例
K×(Σ∪{ε})×Γ
• M=
<K,Σ,Γ,δ,q0,Z0, F>
–
–
–
–
–
–
–
K = {q0,q1,q2, q3, q4, qf }
Σ = { a, b, c }
Γ = { A, Z0 }
δ：状態遷移関数
q0 ：初期状態
Z0：ボトムマーカ
F = { qf }⊂ K
δ( q0, a, Z0 )
δ( q0, a, A )
δ( q0, b, A )
K×Γ*
( q0, A Z0 )
( q0, AA )
(q1,ε), (q3,A)
δ( q1, b, A)
δ( q1, c, Z0)
δ( q2, c, Z0)
( q1,ε)
( q2, Z0 )
( q2, Z0 )
δ( q2,ε, Z0)
δ( q3, b, A )
δ( q3, c, A )
δ( q4, c, A )
( qf, Z0 )
( q3,A )
( q4,ε)
( q4,ε)
δ( q4,ε, Z0)
( qf, Z0 )
42
状態遷移図
43
今日の設問（１番だけ提出）
1. (q0, aaabbbcc, Z0) |*- ?
2. aaabbbcc は受理されるか？
される場合は、その動作の様子を様相表現
で示しなさい。
3. aabbbccc は受理されるか？
44
ここまでのまとめ
• プッシュダウンスタック
• プッシュダウンオートマトン
– 決定性
– 非決定性
• PDAはFAを含む（PDAはFAよりも文字列認
識能力は高い。）＜＝（Why?）
• DPDA は NPDA よりも能力は低い。
（証明はしませんが、事実です。）
45
次回は、チューリングマシンです。
• チューリングマシンは、アルゴリズムや計算
に関する理論の基礎を与えてくれます。
• チューリングマシンと、認識可能な言語との
対応（チョムスキー階層）の話しもやがて出て
きます（第５章）。
• 線形拘束オートマトン（線形有界オートマトン）
も今後導入します。
• 計算量・計算の複雑さなどの話題にも触れま
しょう。お楽しみに！
46
ここまで積み残してきているもの
• Myhill-Nerodeの定理
• （DFAにおける）ポンピング補題など
47

Download Report