東京工科大学 コンピュータサイエンス学部 亀田弘之

Presentation on theme: "東京工科大学 コンピュータサイエンス学部 亀田弘之"— Presentation transcript:

1 東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2016 ー第12回ー 東京工科大学 コンピュータサイエンス学部 亀田弘之 だんだん終わりが見えてきました． もう一息頑張りましょう！

2 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
今後の日程（再） 授業 ７月５日（授業評価アンケート実施） １２日、１９日、２６日。 定期試験 ８月２日（１限9時～、掲示で日時を確認のこと） （注）来週からは、補足追加説明などもしつつ進めます。 　最終回は、試験対策演習＋質問会を開催します。 ・理論も紹介しつつ、過去問を一緒に解きます。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

3 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
到達目標（確認） 言語を処理する自動機械（オートマトン）の種類・仕組み・動作 を自分の言葉で説明できること、 言語には階層があること、プログラミング言語が文脈自由言語 と深くかかわっていることを理解すること、さらには、 言語とオートマトンの密接な相互関係を説明できること、 （与えられた正規表現と等価な有限オートマトンを設計できる） オートマトンの言葉を用いて計算とは何かを説明できること。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

4 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
文法の定義 重要 文法G=（ Vn, Vt, P, S ）： ただし、 Vn: 非終端記号の集合 Vt: 終端記号の集合 P: 書き換え規則の集合 S: 開始記号 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

5 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
文法 文法G=（ Vn, Vt, P, S ）： ただし、 Vn: 非終端記号の集合 　　　　　　<= 構文木構成要素の集合 Vt: 終端記号の集合 <= 単語の集合 P: 書き換え規則の集合 S: 開始記号 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

6 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例１-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 → have, ⑫：V → throw } 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

7 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例１-2 S => NPs VP by ① => PN VP by ② => I VP by ③ => I V NPo by ⑥ => I throw NPo by ⑫ => I throw DET N by ⑤ => I throw a N by ⑦ => I throw a ball by ⑩ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

8 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例１-2 開始記号 適応規則 S => NPs VP by ① => PN VP by ② => I VP by ③ => I V NPo by ⑥ => I throw NPo by ⑫ => I throw DET N by ⑤ => I throw a N by ⑦ => I throw a ball by ⑩ 非終端記号 終端記号 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

9 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例１-2 S => NPs VP by ① => PN VP by ② => I VP by ③ => I V NPo by ⑥ => I throw NPo by ⑫ => I throw DET N by ⑤ => I throw a N by ⑦ => I throw a ball by ⑩ 終端記号のみの列 文 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

10 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例１-2に対する問題 導出を木(tree)として記述せよ。 この文法Gにより生成される文をすべて列挙せよ。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

11 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
言語の定義 言語Lとは、文法Gにより生成されるあらゆる文の集合のこと。 つまり、L＝L(G)。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

12 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
問題 Chomskyの主張が正しいとすると、日本語にも文法が存在し、それは形式文法として記述することができる。このとき、 日本語は正規言語か？　そうであれば証明を、そうでなければ反例を示せ。 日本語は文脈自由文法か？　そうであれば証明を、そうでなければ反例を示せ。 Chomskyの言語理論の限界は何か？ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

13 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
ここまでのまとめ 人間の頭の中には、言語処理装置がある。 すべての文を記憶しているわけではない。 文法として記憶している。 文法とは何か？ 規範文法(Prescriptive Grammar) 記述文法(Descriptive Grammar) 形式文法と形式言語 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

14 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
形式文法と形式言語 文法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 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

15 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
形式文法と形式言語（例） 文法G = （ Vn, Vt, P, S ）： Vn ={S}, Vt={} P={ } 言語L = L(G) = { x | S =*> x } 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

16 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
言語の階層（重要） 言語は文法の種類に応じて、階層構造をなしている。 句構造言語 ⇔ 句構造文法 文脈依存言語 ⇔ 文脈依存文法 文脈自由言語 ⇔ 文脈自由文法 正規言語 ⇔ 正規文法 一般的 特殊的 Chomsky階層(Chomsky Hierarchy)とも言う。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

17 句構造文法 (Phrase-Structure Grammar; PSG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {α→β| α, β ∈ (Vn∪Vt)*} S: 開始記号(S∈Vn) 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

18 句構造文法 (Phrase-Structure Grammar; PSG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {α→β| α, β ∈ (Vn∪Vt)*} S: 開始記号(S∈Vn) 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

19 句構造文法 (Phrase-Structure Grammar; PSG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {α→β| α, β ∈ (Vn∪Vt)*} S: 開始記号(S∈Vn) ここに制限が付くと他の文法になる。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

20 文脈依存文法 (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) 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

21 文脈自由文法 (Context-Free Grammar; CFG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 { X→α| α∈ (Vn∪Vt)*} S: 開始記号(S∈Vn) 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

22 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
生成規則部分の比較 PSG: α→β CSG: αXβ→αγβ CFG: X→α RG: X→aY, X→b ただし、 α，β∈V* ・γ∈V+ X, Y∈Vn ・a, b∈Vt ・V=Vn∪Vt 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

23 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Chomsky階層 重要 PSG CSG CFG RG 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

24 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
文法（言語）とオートマトン 文　　法 　　処理装置 句構造文法(PSG) ⇔ ？ 文脈依存文法(CSG) ⇔ ？ 文脈自由文法(CFG) ⇔ ？ 正規文法(RG) ⇔ ？ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

25 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
文法（言語）とオートマトン 文　　法 　　処理装置 句構造文法(PSG) ⇔ Turing 機械 文脈依存文法(CSG) ⇔ 線形有界オートマトン 文脈自由文法(CFG) ⇔ プッシュダウンオートマトン 正規文法(RG) ⇔ 有限オートマトン これも覚えておいてください． 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

26 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
言語の包含関係 L（PSG) ⊃ L(CSG) ⊃ L(CFG) ⊃ L(RG) このうち、大切なのはCFGとRG。 なぜ大切かというと… 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

27 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
CFGとRG CFG（文脈自由文法）： プログラミング言語設計 コンパイラの構文解析 自然言語処理（機械翻訳・仮名漢字変換） RG（正規文法）： 正規表現（検索・コンパイラの語彙解析） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

28 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
CFGの特徴 CFGには標準形がある。 導出の過程を木で表現できる（導出木の存在）。 解析手法が豊富に知られている。 自然言語処理に部分的に適用できる。 プログラミング言語設計に利用されている。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

29 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
CFGには標準形がある！ これは理論的な証明を行う際に有効です！とうのは、あらゆる文脈自由文法が形式的に同じ形に書けるからです。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

30 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
１．CFGの標準形 Chomskyの標準形 Greibachの標準形 教科書p.174 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

31 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Chomskyの標準形 どの書き換え規則も， 右辺がただ一つの終端記号になっているか， ２個の非終端記号だけである 　という条件を満たしている． つまり，… A →　BC A →　a ただし，A,B,Cは非終端記号，aは終端記号 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

32 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Greibachの標準形 どの書き換え規則も，その右辺が 左端にただ一つの終端記号を有し，かつ， その終端記号に続いて０個以上の非終端記号からなっている， 　という条件を満たしている． つまり，… A →　a A → aB A → aBC A → aBCD … A → aBCD…E…F ただし，A～Fは非終端記号，aは終端記号 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

33 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Chomskyの標準形 任意のCFGにおける書き換え規則群Pは、A→BC　または　A→a　という形だけで表現できる。　 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

34 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Greibachの標準形 任意のCFGにおける書き換え規則群Pは、A→aα　という形だけで表現できる。ただし、X∈Vn, a∈Vt, α∈Vn*。　 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

35 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Chomskyの標準形への変換方法 （教科書 p.177 問題6.9） 　できるようになっておいてください。 試験に出るかもしれません。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

36 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例示 G=< { S, A, B }, { a, b }, P, S > S → bA S → aB A → a A → aS A → bAA B → b B → bS B → aBB これと等価なChomsky標準形文法を求めよう． 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

37 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
結果 S→C1A A→C2S A→C3D1 D1→AA S→C4B B→C5S B→C6D2 D2→BB C1→b C2→a C3→b A→a C4→a C5→b C6→a B→b 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

38 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
練習問題 G=< { S, T, L }, { a, b, +, -, ×, /, [, ] }, P, S > P: S→T+S T →L×T L →[S] S →T-S T →L/T L →a S →T T → L L →b 言語L(G)はどのようなものか？簡単に説明せよ． L(G)を生成するChomsky標準形文法を求めよ． L(G)を生成するGreibach標準形文法を求めよ． 試験に出るかも？ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

39 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
ここまでのまとめ 言語には階層がある（Chomsky階層） 正規言語（正規文法）は語句解析に深い関係がある。 文脈自由言語（文脈自由文法）は構文解析に深い関係がある。 文脈自由文法には標準形が存在する． 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

40 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
その他の重要事項 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

41 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定理１ 与えられたｃｆｇ Gによって生成される言語L(G)が，空集合かそうでないかを決定するアルゴリズムが存在する． 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

42 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定理２ 与えられたｃｆｇ Gによって生成される言語L(G)が，有限集合か無限集合かを決定するアルゴリズムが存在する． （つまり，生成される文が有限個なのか無限個なのかを決定するアルゴリズムが存在する，ということ．） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

43 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定理３ 文法Gが自己埋め込みでないcfgであれば，L(G)は正規集合である． 定義（自己埋め込み）： 　どちらも空でない文字列α1，α2について 　A ＝＞ α1 A α2 となるような非終端記号Aが存在すること． 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

44 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
注 G=< { S }, { a, b }, P, S > P: S→aSa S →aS S →bS S →a S →b 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

45 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
文法の曖昧性 自己埋め込みはｃｆｇを特徴付ける性質の１つ。 これとは別に、“曖昧性”というのも重要な概念です。押さえておきましょう！ （注）ここでいう曖昧性とは、ambiguityです。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

46 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
文法と言語とオートマトン 句構造文法(PSG) 文脈依存文法(CSG) 文脈自由文法(CFG) 正規文法(RG) 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

47 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
言語の階層（重要） 言語は文法の種類に応じて、階層構造をなしている。 句構造言語 ⇔ 句構造文法 文脈依存言語 ⇔ 文脈依存文法 文脈自由言語 ⇔ 文脈自由文法 正規言語 ⇔ 正規文法 一般的 特殊的 Chomsky階層(Chomsky Hierarchy)とも言う。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

48 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
文法（言語）とオートマトン 文　　法 　　処理装置 句構造文法(PSG) ⇔ Turing 機械 文脈依存文法(CSG) ⇔ 線形有界オートマトン 文脈自由文法(CFG) ⇔ プッシュダウンオートマトン 正規文法(RG) ⇔ 有限オートマトン これも覚えておいてください． 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

49 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
再確認（７） オートマトンと形式言語（形式文法）とは相互に密接な関係がある． したがって，形式言語も深く学ぶ価値がある． オートマトンの応用分野： 計算モデル 計算概念の定式化 計算可能性 計算量 その他 形式言語の応用分野： 自然言語処理・音声処理 カナ漢字変換システム 機械翻訳システム 自動通訳システム プログラミング言語とその処理 コンパイラ設計 プログラミング言語設計 その他 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

50 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
ここまでは「オートマトンと形式言語」の関係に重点をおいてきたが、もう一つの側面として、「オートマトンと計算」がある。以下はこれについて概観してみよう！ 重要な話題です！ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

51 Turing認識可能性と Turing決定可能性
Turing-recognizablity Turing-decidability 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

52 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定義：装置Mが言語Lを認識する 装置Mが言語Lを認識する　 　L　＝　｛ w | Mがwを受理(accept)する　｝ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

53 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定義：言語LがTuring認識可能 あるTuringマシンが存在し、それが言語Lを認識するとき、言語LはTuring認識可能であるという。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

54 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Turingマシンの動作について Turingマシンに入力を与え、動作を開始させると以下の３つの結果が生じる。 その入力文字列をacceptする その入力文字列をrejectする 無限ループに陥り、動作が停止しない！ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

55 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定義：決定する あるTuringマシンにある言語の文を入力として与え、動作を開始させたとき、Turingマシンはやがて停止し、その入力をacceptするかrejectするとき、そのTuringマシンはその言語の決定器であるといい、また、そのTuringマシンはその言語を決定するという。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

56 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定義：言語LがTuring決定可能 あるTuringマシンが存在し、それが言語Lを決定するとき、言語LはTuring決定可能であるという。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

57 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例： 言語 はTuring-decidable(Turing決定可能)な 言語である。 チャレンジ問題 　この言語Lを受理するTuringマシンを 　構成してみよう。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

58 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定理 非決定性TMは同等な決定性TMを持つ。 　チャレンジ問題 　　この定理の証明を考えてみよう！ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

59 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
アルゴリズムについて 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

60 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
アルゴリズムとは何か？ “アルゴリズム(algorithm)”という用語はもともと数学の分野で“手続き(procedure or recipe)”とも呼ばれていたもの。素数を発見するためのアルゴリズム(例：エラストテネスの篩法)や最大公約数を計算するアルゴリズム(ユークリッド互除法)などが有名である。 　しかしながら、“何らかの仕事を処理するための指示群”といった程度の概念でとらえられていた。（それでも十分だった…） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

61 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Hilbertの２３の問題 1900年に数学者David Hilbertが、パリで開催された国際数学者会議の講演で、23の問題を提案した。 その第10問題がアルゴリズムに関するものであった。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

62 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
Hilbertの第10問題 多項式(polynomial)pが与えられたとき、その多項式pは整数解のみを持つ多項式であるか否かを判定する手順（アルゴリズム）を考えよ。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

63 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
例： 次の多項式pはx=5,y=3,z=0のときゼロになる。つまり、pは整数解を持つ。与えられた任意の多項式がこのように整数解のみを持つかどうかを判定する処理手続きを考案したい。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

64 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
考えてみてください！ ある種の数学者たちはこのような問題に取り組んでいます！ 皆さんも数学に挑戦してみては？ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

65 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
事実 そんなアルゴリズムは存在しない！ でも、存在しないことを証明することは困難であった。 「存在する」という証明は、例を１つみつければOK . 「存在しない」というのはどうやって証明すればいいのか？ そのような背景からアルゴリズムの理解は深まって行った。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

66 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
歴史的な話 1936年、Alonzo ChurchとAlan Turingの二人がそれぞれ“アルゴリズムの定義”を提案した。 ラムダ計算(λ-clculus)による定義　（Church） Turing machineによる定義　（Turing） この２つの定義は同等であることが示された！ （これをChurch-Turing Thesisという） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

67 Hilbertの第10問題 次のDは決定可能(decidable)か？ D = { p | p は整数解のみを持つ多項式} この問題に対する答えは否定的であった。 しかしながら、この問題はTuring認識可能であることを示すことができる。 このことをもっと単純な問題で見てみよう！ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

68 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
簡単化された問題 D1={ p | pはｘに関する多項式で、整数のみを解として持つ} TM M1はD1を認識する。 M1： ｘに関する多項式pを入力とする。 多項式pの値を、以下のxについて順次計算し、どこかでp=0となったらそのpをacceptする。 x=0, 1, -1, 2, -2, 3, -3, 4, -4, … 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

69 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
これは認識可能であるが決定可能ではない。また、多変数への拡張は可能である。 しかしながら、これらは決定可能ではないという問題点がある。 だが、… 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

70 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
定理 多項式 　がx=aでp=0とする。このとき、 　とするとき以下の不等式が成り立つ。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

71 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
この定理により、先の「簡単化された問題」は決定的であることが分かる。 しかしながら、一般的な問題つまりHilbertの第10問題は決定可能なのだろうか？ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

72 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
1970年、Yuri MatijasevicによりHilbertの第10問題に対するアルゴリズムは存在しないことが証明された。 （ Matijasevic の定理） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

73 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
おまけ 無限と有限について 整数は自然数と同じだけある（個数は同じ）。 有理数は自然数と同じだけある。 無理数は自然数よりもたくさんある。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

74 2016年度 オートマトンと形式言語 東京工科大学コンピュータサイエンス学部
まとめ オートマトンと形式言語 オートマトンと計算量 形式言語と計算量（複雑さ） 「複雑さ」という用語は、コンピュータサイエンスの分野における重要なキーワードです。後日お話します。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部