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

形式言語とオートマトン2014
ー第11&12日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
だんだん終わりが見えてきました.
そろそろ全体をまとめていきましょう.
問題1.1
• 次のものは、2つの有限オートマトンM1とM2
の状態遷移図である。それぞれについて以
下の問に答えなさい。
a.初期状態はどれか。
b.最終状態はどれか。
c.入力 aabb のときのオートマトンの状態遷移
の系列はどうなるか。
d.入力 aabb は受理されるか。
e.空文字列εは受理されるか。
2
©Tokyo University of Technology, School of Computer Science, H.Kameda
問題1.2
• 前述の問題1.1でのオートマトンM1とM2を形
式的に記述しなさい。
3
©Tokyo University of Technology, School of Computer Science, H.Kameda
問題1.3
• 有限オートマトンMを形式的記述が、
({ q1, q2, q3, q4, q5 },{u, d},δ, q3,{q3})と
なっているとする。ただし、関数δは以下のよ
うな表で与えられるとする。このとき、このオ
ートマトンの状態遷移図はどうなるか。
現在の
状態
q1
q2
q3
q4
q5
次の状態
入力 u
d
q1
q1
q2
q3
q4
q2
q3
q4
q5
q5
4
©Tokyo University of Technology, School of Computer Science, H.Kameda
さて、今回も復習から!
• ざっと見ていきましょう.
(記憶をリフレッシュしましょう。
短期記憶ではリハーサルが大切。
(心理学・脳神経科学の知見より))
いろんなことを思い出しな
がら話しを聞いてください。
5
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(1)
• 有限オートマトン(FA)
– FAの定義と記述法
テープ上を一方向に動くヘッド
(テープ上の記号を順次読みながら内部状態を遷移)
M = <K, Σ, δ, q0, F> (5つ組)
状態遷移図
様相(configuration)
– FAの種類
決定性FA(DFA)
非決定性FA(ε遷移のあるものとないもの)
– 言語認識能力はどのFAでも同じ。
正規言語(正規表現)を認識
6
©Tokyo University of Technology, School of Computer Science, H.Kameda
有限オートマトンのイメージ
• FAの概観
a1 a2
セル
入力記号
・・・
ai-1 ai
・・・
・・・
an
qk
入力テープ
内部状態
ヘッド
7
確認(2)
•
正規表現を認識するFAの存在とその構成法
1.
2.
3.
4.
5.
正規表現αが与えられる。
正規表現αに対して、ε-NFA を構成する。
ε-NFA をDFAに書き換える。
DFAを状態数最少のDFA(Min-DFA)に書き換える。
Min-DFAをシミュレートするプログラムを作成する。
8
©Tokyo University of Technology, School of Computer Science, H.Kameda
研究課題
DFAをシミュレートするプログラム
• 基本的には状態遷移関数を実装すればOK。
• コンパイラなどでの字句解析では、単語(文字
列)の読み込みに関してプログラミング上の工
夫が必要。
• Prologで書けばもっと簡単!? 状態遷移表を
Prologで記述すればいいだけ!
• いろんな言語で実装してみてください。
(後期の授業「言語プロセッサ」で学びます。)
9
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(3)
• プッシュダウンオートマトン(PDA)
– スタックの定義
データ構造:
・配列(またはアレイ)
・リスト
・スタック
・キュー など
スタックの構造と動作(pop-up と push-down)
LIFO (Last-In First-Out) 型のメモリ
– PDAの定義と記述法
テープ上を一方向に動くヘッド+スタックメモリ
(テープの記号を順次読み、スタック上の記号を順次読
み書きしながら内部状態を遷移)
M = < K, Σ, Γ,δ, q0, Z0, F > (7つ組)
状態遷移図
様相(configuration)
10
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(4)
スタックとPDAのイメージ図
Pop up
Push down
LIFO (Last In First Out)
最後に入れたものが最初に取り出される。
11
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(5)
• プッシュダウンオートマトン(PDA)
– PDAの種類
決定性プッシュダウンオートマトン
Deterministic pushdown automaton (DPDA)
非決定性プッシュダウンオートマトン
Nondeterministic pushdown automaton (NPDA)
– 言語認識能力はNPDAの方が高い。
FAは正規言語(正規表現)を認識
NPDAは文脈自由言語を認識
DPDAよりもNPDAの方が言語認識能力大
12
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(6)
• チューリングマシン(Turing Machine; TM)
– TMの定義と記述法
 テープ上を左右どちらにも動けるヘッド
(テープ上の記号を順次読み、テープ上に時として記号を書き込み
ながら、そのたびごとに内部状態を遷移)
 M = < K, Γ, Σ, δ, q0, B, F > (7つ組)
 状態遷移図
 様相(configuration)
– TMの種類
 決定性TM(DTM)
 非決定性TM(NTM)
– 言語認識能力はどのTMでも同じ。
 句構造言語(句構造文法に適った文)を認識
13
©Tokyo University of Technology, School of Computer Science, H.Kameda
補足
• 有限オートマトンは記憶容量有限な装置
• プッシュダウンオートマトンは、記憶容量に制
限のない装置(スタックは必要に応じて情報
を蓄積できる)
• 有限オートマトンは正規言語、プッシュダウン
オートマトンは文脈自由言語をそれぞれ認識
することができる。それ以上一般の言語の認
識するにはチューリングマシンが必要。
14
©Tokyo University of Technology, School of Computer Science, H.Kameda
質問
• 現在のコンピュータは、どの種類のオートマト
ンと考えることができるか? その理由ととも
に答えなさい。
15
©Tokyo University of Technology, School of Computer Science, H.Kameda
質問
• オートマトン(の理論)が利用されている例を
5つ挙げなさい。
1. パックマンなどのゲーム
2. gccなどのコンパイラ(言語プロセッサ)
3. それから...
16
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(7)
• オートマトンと形式言語(形式文法)とは相互
に密接な関係がある.
• したがって,形式言語も深く学ぶ価値がある.
• オートマトンの応用分野:
– 計算モデル
• 計算概念の定式化
• 計算可能性
• 計算量
– その他
• 形式言語の応用分野:
– 自然言語処理・音声処理
• カナ漢字変換システム
• 機械翻訳システム
• 自動通訳システム
– プログラミング言語とその処理
• コンパイラ設計
• プログラミング言語設計
– その他
17
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(8):言語の形式的定義
• 単語w: X1, X2, X3, ・・・, Xn (はじめに単語ありき)
• 語彙V (Vocabulary) : 単語の集合
V = { X1, X2, X3, ・・・, Xn } (有限集合)
• 文(sentence): 単語の並び(単語の列)
(注)
– Vの要素( X1 や X2 など)は単語
– Xa Xb Xc Xd など,単語の並びは何でも文と考える.
– でも何でも良いわけではない。
18
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(9):考察
• 文は無限個存在する。
(単語は有限個)
• 言語L(例えば英語)として意味のあるものと
そうでないものとが混ざっている。
⇒ 言語Lとして意味のある文をすべて集めた集合
は、1つの言語(今の場合はL)を定める。
⇒ 言語Lとして意味があるものとないものとを
区別したい。
つまり、任意の文(単語列)に対して、それが
言語Lの文かそうではないのかを判定したい。
19
©Tokyo University of Technology, School of Computer Science, H.Kameda
©Tokyo University of Technology,
School of Computer Science,
20
21
©Tokyo University of Technology, School of Computer Science, H.Kameda
• そんなことできるのだろうか?
でも、人間はやっているよ!
じゃあ、できるんだね!(信念)
自動機械(オートマトン)を作ってみよう!
22
©Tokyo University of Technology, School of Computer Science, H.Kameda
作成のためのアイデア
• はじめに言語Lの文すべてを知っているなら
ば、下記のような機械ができる。
文S1
オートマトン
S1 S2 S3
… Sn
S1は言語Lの
文だよ!
23
©Tokyo University of Technology, School of Computer Science, H.Kameda
問題点1
• でも、
「言語Lの文すべてを知っている」
なんて、不可能だよ!
• 例:「2008年6月23日、形式言語とオートマト
ンの授業が、講実403教室で、パワーポイン
トを用いて行われた。」 という文をあなたは
事前に知っていましたか?
24
©Tokyo University of Technology, School of Computer Science, H.Kameda
問題点2
• もし何らかの方法により、事前に言語Lのすべての文
を知っていたとしても...
s = get_sentence();
if ( s ∈ Lの文の集合 ) then
s は Lの文である
else
s は Lの文ではない
end if
Lの文の集合が無限集合のときは、このプログラムは
停止しないことがある!!!
25
©Tokyo University of Technology, School of Computer Science, H.Kameda
それではどうしようか?!
26
©Tokyo University of Technology, School of Computer Science, H.Kameda
ここまでのまとめ
• 言語
– 意味のある文(言語Lの文)の集合
• 文法の必要性
– ある言語(例えば日本語)の文すべてを
あらかじめ知っているなんてことは不可能!
• オートマトン
– ある文が対象としている言語Lの文なのかを自動
判定する装置
27
©Tokyo University of Technology, School of Computer Science, H.Kameda
どうも文法が大切らしい。
もう少し文法について学んでみよう!
28
©Tokyo University of Technology, School of Computer Science, H.Kameda
ホントにしゃべれるよ
うになるのかなぁ
普遍文法という発想
• すべてのヒトは、
– 言語に依存しない普遍的な処理能力をもった装
置(device)を生得的に持っており、
– 個別言語に関する知識は後天的に獲得されるか
らだ。
僕にもこん
な装置がほ
しいなぁ…
これが私の基
本的考えです。
29
©Tokyo University of Technology, School of Computer
Science, H.Kameda
写真の出典:Wikipediaより
• その知識は、「文法」という形で獲得される。
• Chomskyはそのように考えた。
• それでは彼の考えを見てみよう。
30
©Tokyo University of Technology, School of Computer Science, H.Kameda
文法の定義
重要
• 文法G=( Vn, Vt, P, S ):
– ただし、
•
•
•
•
Vn:
Vt:
P:
S:
非終端記号の集合
終端記号の集合
書き換え規則の集合
開始記号
31
©Tokyo University of Technology, School of Computer Science, H.Kameda
文法
• 文法G=( Vn, Vt, P, S ):
– ただし、
• Vn: 非終端記号の集合
<= 構文木構成要素の集合
• Vt: 終端記号の集合
<= 単語の集合
• P: 書き換え規則の集合
• S: 開始記号
32
©Tokyo University of Technology, School of Computer Science, H.Kameda
例1-1
• G=(Vn, Vt, P, S)
– Vn = { S, NPs, NPo, VP, PN, DET, N }
– Vt = { I, You, have, throw, a, the, book, ball }
– P = { ①:S → NPs VP,
②:NPs →
PN,
③:PN → I,
④:PN → You,
⑤:NPo → DET N,
⑥:VP → V NPo,
⑦:DET → a,
⑧:DET → the,
⑨:N → book,
⑩:N → ball,
⑪:V©Tokyo
→ have,
⑫:V
→ throw
} 33
University of Technology, School
of Computer
Science, H.Kameda
例1-2
• S =>
=>
=>
=>
=>
=>
=>
=>
NPs VP
PN VP
I
VP
I V NPo
I throw NPo
I throw DET N
I throw a N
I throw a ball
①
②
③
⑥
⑫
by ⑤
by ⑦
by ⑩
by
by
by
by
by
34
©Tokyo University of Technology, School of Computer Science, H.Kameda
開始記号
• S =>
=>
=>
=>
=>
=>
=>
=>
例1-2
非終端記号
NPs VP
PN VP
I
VP
I V NPo
I throw NPo
I throw DET N
I throw a N
I throw a ball
適応規則
①
②
③
⑥
⑫
by ⑤
by ⑦
by ⑩
by
by
by
by
by
終端記号
35
©Tokyo University of Technology, School of Computer Science, H.Kameda
例1-2
• S =>
=>
=>
=>
=>
=>
=>
=>
文
NPs VP
PN VP
I
VP
I V NPo
I throw NPo
I throw DET N
I throw a N
I throw a ball
①
②
③
⑥
⑫
by ⑤
by ⑦
by ⑩
by
by
by
by
by
終端記号のみの列
36
©Tokyo University of Technology, School of Computer Science, H.Kameda
例1-2に対する問題
• これは木(tree)として記述せよ。
• この文法Gにより生成される文をすべて列挙
せよ。
37
©Tokyo University of Technology, School of Computer Science, H.Kameda
言語の定義
• 言語Lとは、文法Gにより生成されるあらゆる
文の集合のこと。
• つまり、L=L(G)。
38
©Tokyo University of Technology, School of Computer Science, H.Kameda
問題
• Chomskyの主張が正しいとすると、日本語に
も文法が存在し、それは形式文法として記述
することができる。このとき、
1.日本語は正規言語か? そうであれば証明
を、そうでなければ反例を示せ。
2.日本語は文脈自由文法か? そうであれば
証明を、そうでなければ反例を示せ。
3.Chomskyの言語理論の限界は何か?
39
©Tokyo University of Technology, School of Computer Science, H.Kameda
ここまでのまとめ
•
•
•
•
人間の頭の中には、言語処理装置がある。
すべての文を記憶しているわけではない。
文法として記憶している。
文法とは何か?
– 規範文法(Prescriptive Grammar)
– 記述文法(Descriptive Grammar)
• 形式文法と形式言語
40
©Tokyo University of Technology, School of Computer Science, H.Kameda
形式文法と形式言語
• 文法G = ( Vn, Vt, P, S ):
– ただし、
• Vn(非終端記号の集合): 0 < #Vn < +∞
• Vt: 終端記号の集合:
0 < #Vt < +∞
• P: 書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
• S:
開始記号(S∈Vn)
• 言語L = L(G) = { x | S =*> x }
– ただし、S => ・・・ => x ∈ Vt
41
©Tokyo University of Technology, School of Computer Science, H.Kameda
形式文法と形式言語(例)
• 文法G = ( Vn, Vt, P, S ):
– Vn ={S}, Vt={}
– P={ }
• 言語L = L(G) = { x | S =*> x }
42
©Tokyo University of Technology, School of Computer Science, H.Kameda
言語の階層(重要)
• 言語は文法の種類に応じて、階層構造をなし
ている。
– 句構造言語
– 文脈依存言語
– 文脈自由言語
– 正規言語
⇔
⇔
⇔
⇔
句構造文法
文脈依存文法
文脈自由文法
正規文法
Chomsky階層
(Chomsky Hierarchy)
とも言う。
一般的
特殊的
43
©Tokyo University of Technology, School of Computer Science, H.Kameda
句構造文法
(Phrase-Structure Grammar; PSG)
• 文法G = ( Vn, Vt, P, S ):
– Vn(非終端記号の集合):
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
44
©Tokyo University of Technology, School of Computer Science, H.Kameda
句構造文法
(Phrase-Structure Grammar; PSG)
• 文法G = ( Vn, Vt, P, S ):
– Vn(非終端記号の集合):
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
45
©Tokyo University of Technology, School of Computer Science, H.Kameda
句構造文法
(Phrase-Structure Grammar; PSG)
• 文法G = ( Vn, Vt, P, S ):
– Vn(非終端記号の集合):
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{α→β| α, β ∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
ここに制限が付くと他の
文法になる。
46
©Tokyo University of Technology, School of Computer Science, H.Kameda
文脈依存文法
(Context-Sensitive Grammar; CSG)
• 文法G = ( Vn, Vt, P, S ):
– Vn(非終端記号の集合): 0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{αXβ→αγβ| α, β ∈ (Vn∪Vt)*, X∈Vn,
γ∈ (Vn∪Vt)+ }
– S:
開始記号(S∈Vn)
47
©Tokyo University of Technology, School of Computer Science, H.Kameda
文脈自由文法
(Context-Free Grammar; CFG)
• 文法G = ( Vn, Vt, P, S ):
– Vn(非終端記号の集合):
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{ X→α| α∈ (Vn∪Vt)*}
– S:
開始記号(S∈Vn)
48
©Tokyo University of Technology, School of Computer Science, H.Kameda
正規文法
(Regular Grammar; RG)
• 文法G = ( Vn, Vt, P, S ):
– Vn(非終端記号の集合):
0 < #Vn < +∞
– Vt:
終端記号の集合: 0 < #Vt < +∞
– P:
書き換え規則の集合
{X→aY, X→b| X,Y∈Vn, a,b ∈ Vt*}
– S:
開始記号(S∈Vn)
49
©Tokyo University of Technology, School of Computer Science, H.Kameda
生成規則部分の比較
•
•
•
•
PSG:
CSG:
CFG:
RG:
α→β
αXβ→αγβ
X→α
X→aY, X→b
– ただし、
• α,β∈V*
• X, Y∈Vn
・γ∈V+
・a, b∈Vt
・V=Vn∪Vt
50
©Tokyo University of Technology, School of Computer Science, H.Kameda
重要
Chomsky階層
PSG
CSG
CFG
RG
©Tokyo University of Technology,
School of Computer Science,
51
文法(言語)とオートマトン
----------------------------------------------------文 法
処理装置
----------------------------------------------------• 句構造文法(PSG)
⇔ ?
• 文脈依存文法(CSG)
⇔ ?
• 文脈自由文法(CFG)
⇔ ?
• 正規文法(RG)
⇔ ?
----------------------------------------------------52
©Tokyo University of Technology, School of Computer Science, H.Kameda
文法(言語)とオートマトン
---------------------------------------------------------------文 法
処理装置
---------------------------------------------------------------• 句構造文法(PSG)
⇔
Turing 機械
• 文脈依存文法(CSG) ⇔
線形有界オートマトン
• 文脈自由文法(CFG) ⇔
プッシュダウンオートマトン
• 正規文法(RG)
⇔
有限オートマトン
---------------------------------------------------------------これも覚えておいてください.
53
©Tokyo University of Technology, School of Computer Science, H.Kameda
言語の包含関係
L(PSG) ⊃ L(CSG) ⊃ L(CFG) ⊃ L(RG)
このうち、大切なのはCFGとRG。
なぜ大切か
というと…
54
©Tokyo University of Technology, School of Computer Science, H.Kameda
CFGとRG
• CFG(文脈自由文法):
– プログラミング言語設計
– コンパイラの構文解析
– 自然言語処理(機械翻訳・仮名漢字変換)
• RG(正規文法):
– 正規表現(検索・コンパイラの語彙解析)
55
©Tokyo University of Technology, School of Computer Science, H.Kameda
CFGの特徴
1.
2.
3.
4.
5.
CFGには標準形がある。
導出の過程を木で表現できる(導出木の存在)。
解析手法が豊富に知られている。
自然言語処理に部分的に適用できる。
プログラミング言語設計に利用されている。
56
©Tokyo University of Technology, School of Computer Science, H.Kameda
CFGには標準形がある!
• これは理論的な証明を行う際に有効です!と
うのは、あらゆる文脈自由文法が形式的に同
じ形に書けるからです。
57
©Tokyo University of Technology, School of Computer Science, H.Kameda
1.CFGの標準形
• Chomskyの標準形
• Greibachの標準形
教科書p.174
58
©Tokyo University of Technology, School of Computer Science, H.Kameda
Chomskyの標準形
• どの書き換え規則も,
– 右辺がただ一つの終端記号になっているか,
– 2個の非終端記号だけである
という条件を満たしている.
つまり,…
• A → BC
•A → a
• ただし,A,B,Cは非終端記号,aは終端記号
59
©Tokyo University of Technology, School of Computer Science, H.Kameda
Greibachの標準形
• どの書き換え規則も,その右辺が
– 左端にただ一つの終端記号を有し,かつ,
– その終端記号に続いて0個以上の非終端記号か
らなっている,
という条件を満たしている.
つまり,…
•A → a
• A → aB
•A → aBC
•A → aBCD
•…
•A → aBCD…E…F
ただし,A~Fは非終端記号,aは終端記号
60
©Tokyo University of Technology, School of Computer Science, H.Kameda
Chomskyの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→BC または A→a という形だけで表現
できる。
61
©Tokyo University of Technology, School of Computer Science, H.Kameda
Greibachの標準形
• 任意のCFGにおける書き換え規則群Pは、
A→aα という形だけで表現できる。ただし、
X∈Vn, a∈Vt, α∈Vn*。
62
©Tokyo University of Technology, School of Computer Science, H.Kameda
Chomskyの標準形への変換方法
(教科書 p.177 問題6.9)
できるようになっておいてください。
試験に出るかもしれません。
63
©Tokyo University of Technology, School of Computer Science, H.Kameda
例示
• G=< { S, A, B }, { a, b }, P, S >
S → bA
A→ a
B → b
S → aB
A → aS
B → bS
A → bAA
B → aBB
これと等価なChomsky標準形
文法を求めよう.
64
©Tokyo University of Technology, School of Computer Science, H.Kameda
結果
S→C1A
D1→AA
B→C6D2
C2→a
C4→a
B→b
A→C2S
S→C4B
D2→BB
C3→b
C5→b
A→C3D1
B→C5S
C1→b
A→a
C6→a
65
©Tokyo University of Technology, School of Computer Science, H.Kameda
練習問題
G=< { S, T, L }, { a, b, +, -, ×, /, [, ] }, P, S >
P:
S→T+S
S →T-S
S →T
T →L×T
T →L/T
T→L
L →[S]
L →a
L →b
1. 言語L(G)はどのようなものか?簡単に説明せよ.
2. L(G)を生成するChomsky標準形文法を求めよ.
3. L(G)を生成するGreibach標準形文法を求めよ.
試験に出るかも?
66
©Tokyo University of Technology, School of Computer Science, H.Kameda
ここまでのまとめ
• 言語には階層がある(Chomsky階層)
• 正規言語(正規文法)は語句解析に深い関係
がある。
• 文脈自由言語(文脈自由文法)は構文解析に
深い関係がある。
• 文脈自由文法には標準形が存在する.
67
©Tokyo University of Technology, School of Computer Science, H.Kameda
その他の重要事項
68
©Tokyo University of Technology, School of Computer Science, H.Kameda
定理1
• 与えられたcfg Gによって生成される言語
L(G)が,空集合かそうでないかを決定するア
ルゴリズムが存在する.
69
©Tokyo University of Technology, School of Computer Science, H.Kameda
定理2
• 与えられたcfg Gによって生成される言語
L(G)が,有限集合か無限集合かを決定する
アルゴリズムが存在する.
(つまり,生成される文が有限個なのか無限
個なのかを決定するアルゴリズムが存在する,
ということ.)
70
©Tokyo University of Technology, School of Computer Science, H.Kameda
定理3
• 文法Gが自己埋め込みでないcfgであれば,
L(G)は正規集合である.
定義(自己埋め込み):
どちらも空でない文字列α1,α2について
A => α1 A α2 となるような非終端記号Aが
存在すること.
71
©Tokyo University of Technology, School of Computer Science, H.Kameda
注
• G=< { S }, { a, b }, P, S >
P:
S→aSa
S →aS
S →a
S →b
S →bS
72
©Tokyo University of Technology, School of Computer Science, H.Kameda
文法の曖昧性
• 自己埋め込みはcfgを特徴付ける性質の1つ。
• これとは別に、“曖昧性”というのも重要な概念
です。押さえておきましょう!
(注)ここでいう曖昧性とは、ambiguityです。
73
©Tokyo University of Technology, School of Computer Science, H.Kameda
文法と言語とオートマトン
•
•
•
•
句構造文法(PSG)
文脈依存文法(CSG)
文脈自由文法(CFG)
正規文法(RG)
74
©Tokyo University of Technology, School of Computer Science, H.Kameda
言語の階層(重要)
• 言語は文法の種類に応じて、階層構造をなし
ている。
– 句構造言語
– 文脈依存言語
– 文脈自由言語
– 正規言語
⇔
⇔
⇔
⇔
句構造文法
文脈依存文法
文脈自由文法
正規文法
Chomsky階層
(Chomsky Hierarchy)
とも言う。
一般的
特殊的
75
©Tokyo University of Technology, School of Computer Science, H.Kameda
文法(言語)とオートマトン
---------------------------------------------------------------文 法
処理装置
---------------------------------------------------------------• 句構造文法(PSG)
⇔
Turing 機械
• 文脈依存文法(CSG) ⇔
線形有界オートマトン
• 文脈自由文法(CFG) ⇔
プッシュダウンオートマトン
• 正規文法(RG)
⇔
有限オートマトン
---------------------------------------------------------------これも覚えておいてください.
76
©Tokyo University of Technology, School of Computer Science, H.Kameda
おまけの絵(曖昧性,ambiguity)
77
©Tokyo University of Technology, School of Computer Science, H.Kameda
確認(7)
• オートマトンと形式言語(形式文法)とは相互
に密接な関係がある.
• したがって,形式言語も深く学ぶ価値がある.
• オートマトンの応用分野:
– 計算モデル
• 計算概念の定式化
• 計算可能性
• 計算量
– その他
• 形式言語の応用分野:
– 自然言語処理・音声処理
• カナ漢字変換システム
• 機械翻訳システム
• 自動通訳システム
– プログラミング言語とその処理
• コンパイラ設計
• プログラミング言語設計
– その他
78
©Tokyo University of Technology, School of Computer Science, H.Kameda
• ここまでは「オートマトンと形式言語」の関係
に重点をおいてきたが、もう一つの側面として
、「オートマトンと計算」がある。以下はこれに
ついて概観してみよう!
79
©Tokyo University of Technology, School of Computer Science, H.Kameda
Turing認識可能性と
Turing決定可能性
• Turing-recognizablity
• Turing-decidability
80
©Tokyo University of Technology, School of Computer Science, H.Kameda
定義:装置Mが言語Lを認識する
• 装置Mが言語Lを認識する 
L = { w | Mがwを受理(accept)する }
81
©Tokyo University of Technology, School of Computer Science, H.Kameda
定義:言語LがTuring認識可能
• あるTuringマシンが存在し、それが言語Lを
認識するとき、言語LはTuring認識可能であ
るという。
82
©Tokyo University of Technology, School of Computer Science, H.Kameda
Turingマシンの動作について
• Turingマシンに入力を与え、動作を開始させ
ると以下の3つの結果が生じる。
1. その入力文字列をacceptする
2. その入力文字列をrejectする
3. 無限ループに陥り、動作が停止しない!
83
©Tokyo University of Technology, School of Computer Science, H.Kameda
定義:決定する
• あるTuringマシンにある言語の文を入力とし
て与え、動作を開始させたとき、Turingマシン
はやがて停止し、その入力をacceptするか
rejectするとき、そのTuringマシンはその言語
の決定器であるといい、また、そのTuringマ
シンはその言語を決定するという。
84
©Tokyo University of Technology, School of Computer Science, H.Kameda
定義:言語LがTuring決定可能
• あるTuringマシンが存在し、それが言語Lを
決定するとき、言語LはTuring決定可能であ
るという。
85
©Tokyo University of Technology, School of Computer Science, H.Kameda
例:
• 言語
L  {0 | n  0}
2n
はTuring-decidable(Turing決定可能)な
言語である。
チャレンジ問題
この言語Lを受理するTuringマシンを
構成してみよう。
86
©Tokyo University of Technology, School of Computer Science, H.Kameda
定理
• 非決定性TMは同等な決定性TMを持つ。
チャレンジ問題
この定理の証明を考えてみよう!
87
©Tokyo University of Technology, School of Computer Science, H.Kameda
アルゴリズムについて
88
©Tokyo University of Technology, School of Computer Science, H.Kameda
アルゴリズムとは何か?
• “アルゴリズム(algorithm)”という用語はもと
もと数学の分野で“手続き(procedure or
recipe)”とも呼ばれていたもの。素数を発見
するためのアルゴリズム(例:エラストテネス
の篩法)や最大公約数を計算するアルゴリズ
ム(ユークリッド互除法)などが有名である。
しかしながら、“何らかの仕事を処理するた
めの指示群”といった程度の概念でとらえら
れていた。(それでも十分だった…)
89
©Tokyo University of Technology, School of Computer Science, H.Kameda
Hilbertの23の問題
• 1900年に数学者David Hilbertがパリで開催
された国際数学者会議の講演で、23の問題
を提案した。
その第10問題がアルゴリズムに関するもの
であった。
90
©Tokyo University of Technology, School of Computer Science, H.Kameda
Hilbertの第10問題
• 多項式(polynomial)pが与えられたとき、その
多項式pは整数解のみを持つ多項式である
のか否かを判定する手順(アルゴリズム)を
考えよ。
91
©Tokyo University of Technology, School of Computer Science, H.Kameda
例:
• 次の多項式pはx=5,y=3,z=0のときゼロにな
る。つまり、pは整数解を持つ。与えられた任
意の多項式がこのように整数解のみを持つ
かどうかを判定する処理手続きを考案したい
。
6 x yz  3xy  x 10
3
2
2
3
92
©Tokyo University of Technology, School of Computer Science, H.Kameda
考えてみてください!
• ある種の数学者たちはこのような問題に取り
組んでいます!
皆さんも数学者に挑戦してみては?
93
©Tokyo University of Technology, School of Computer Science, H.Kameda
事実
• そんなアルゴリズムは存在しない!
• でも、存在しないことを証明することは困難で
あった。
• 「存在する」という証明は、例を1つみつけれ
ばOK .
• 「存在しない」というのはどうやって証明すれ
ばいいのか?
• そのような背景からアルゴリズムの理解は深
まって行った。
94
©Tokyo University of Technology, School of Computer Science, H.Kameda
歴史的な話
• 1936年、Alonzo ChurchとAlan Turingの二
人の“アルゴリズムの定義”が得られた。
– ラムダ計算(λ-clculus)による定義 (Church)
– Turing machineによる定義 (Turing)
この2つの定義は同等であることが示された!
(これをChurch-Turing Thesisという)
95
©Tokyo University of Technology, School of Computer Science, H.Kameda
Hilbertの第10問題
• 次のDは決定可能(decidable)か?
D = { p | p は整数解のみを持つ多項式}
この問題に対する答えは否定的であった。
しかしながら、この問題はTuring認識可能で
あることを示すことができる。
このことをもっと単純な問題で見てみよう!
96
©Tokyo University of Technology, School of Computer Science, H.Kameda
簡単化された問題
• D1={ p | pはxに関する多項式で、整数のみを
解として持つ}
• TM M1はD1を認識する。
• M1:
xに関する多項式pを入力とする。
1. 多項式pの値を、以下のxについて順次計算し、
どこかでp=0となったらそのpをacceptする。
x=0, 1, -1, 2, -2, 3, -3, 4, -4, …
97
©Tokyo University of Technology, School of Computer Science, H.Kameda
• これは認識可能であるが決定可能ではない。
また、多変数への拡張は可能である。
• しかしながら、これらは決定可能ではないと
いう問題点がある。
• だが、…
98
©Tokyo University of Technology, School of Computer Science, H.Kameda
定理
• 多項式
p  c1 x  c2 x
n
n1
  cn x  cn1
がx=aでp=0とする。このとき、
cmax  {c1 , c2 ,, cn1}
とするとき以下の不等式が成り立つ。
cmax
| a | (n  1)
| c1 |
99
©Tokyo University of Technology, School of Computer Science, H.Kameda
• この定理により、先の「簡単化された問題」は
決定的であることが分かる。
• しかしながら、一般的な問題つまりHilbertの
第10問題は決定可能なのだろうか?
100
©Tokyo University of Technology, School of Computer Science, H.Kameda
• 1970年、Yuri MatijasevicによりHilbertの第
10問題に対するアルゴリズムは存在しないこ
とが証明された。
( Matijasevic の定理)
101
©Tokyo University of Technology, School of Computer Science, H.Kameda
おまけ
• 無限と有限について
– 整数は自然数と同じだけある(個数は同じ)。
– 有理数は自然数と同じだけある。
– 無理数は自然数よりもたくさんある。
102
©Tokyo University of Technology, School of Computer Science, H.Kameda
まとめ
• オートマトンと形式言語
• オートマトンと計算量
• 形式言語と計算量(複雑さ)
103
©Tokyo University of Technology, School of Computer Science, H.Kameda