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

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

Download Report