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

東京工科大学コンピュータサイエンス学部亀田弘之
形式言語とオートマトン2015 ー第14＆最終回ー東京工科大学コンピュータサイエンス学部亀田弘之だんだん終わりが見えてきました．そろそろ全体をまとめていきましょう．

©Tokyo University of Technology, School of Computer Science, H.Kameda
今後の日程授業７月１４日、２１日の２日のみ。定期試験７月２８日（掲示で日時を確認のこと）（注）来週は試験対策演習＋質問会を開催します。・過去問を一緒に解きます。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

授業概要（確認）　日本語や英語も、JavaやCなどのプログラミング言語もともに“言語”である。それではこれらの言語にはどのような共通点・相違点があるのだろうか？　はたまた、人間が日本語や英語を理解し行動する処理と、コンピュータがプログラミング言語を理解し実行する処理の間には何か関係があるのだろうか？　　本講義では、学生諸君がこの疑問に対して明快に答えることができ、かつ、“コンピュータ”および“計算”の本質を知るきっかけを得ることができることを目指して、“形式言語”という概念を導入し一段高い観点から言語を概観し、言語処理装置でありかつ今日のコンピュータの理論モデルでもあるオートマトンについて詳しく学ぶことを目指す。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

到達目標（確認）言語を処理する自動機械（オートマトン）の種類・仕組み・動作を自分の言葉で説明できること、言語には階層があること、プログラミング言語が文脈自由言語と深くかかわっていることを理解すること、さらには、言語とオートマトンの密接な相互関係を説明できること、（与えられた正規表現と等価な有限オートマトンを設計できる）オートマトンの言葉を用いて計算とは何かを説明できること。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

問題1.1 次のものは、２つの有限オートマトンM1とM2の状態遷移図である。それぞれについて以下の問に答えなさい。初期状態はどれか。最終状態はどれか。入力 aabb のときのオートマトンの状態遷移の系列はどうなるか。入力 aabb は受理されるか。空文字列εは受理されるか。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

問題1.2 前述の問題1.1でのオートマトンM1とM2を形式的に記述しなさい。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

問題1.3 有限オートマトンMを形式的記述が、（｛ q1, q2, q3, q4, q5 ｝,｛u, d｝,δ, q3,｛q3｝）となっているとする。ただし、関数δは以下のような表で与えられるとする。このとき、このオートマトンの状態遷移図はどうなるか。現在の状態　　　次の状態入力 u d q1 q2 q3 q4 q5 　　　 q1 q2 　　　 q1 q3 　　　 q2 q4 　　　 q3 q5 　　　 q4 q5 ©Tokyo University of Technology, School of Computer Science, H.Kameda

いろんなことを思い出しながら話しを聞いてください。
さて、今回も復習から！ざっと見ていきましょう．（記憶をリフレッシュしましょう。　短期記憶ではリハーサルが大切。　　（心理学・脳神経科学の知見より））いろんなことを思い出しながら話しを聞いてください。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認(1) 有限オートマトン(FA) FAの定義と記述法テープ上を一方向に動くヘッド（テープ上の記号を順次読みながら内部状態を遷移） M = <K, Σ, δ, q0, F> 　（５つ組）状態遷移図様相（configuration） FAの種類決定性FA（DFA）非決定性FA（ε遷移のあるものとないもの）言語認識能力はどのFAでも同じ。正規言語（正規表現）を認識 ©Tokyo University of Technology, School of Computer Science, H.Kameda

有限オートマトンのイメージ qk FAの概観 a1 a2 ai-1 ai an セル入力記号入力テープヘッド内部状態・・・・・・

確認（２）正規表現を認識するFAの存在とその構成法正規表現αが与えられる。正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数最少のDFA(Min-DFA)に書き換える。 Min-DFAをシミュレートするプログラムを作成する。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

研究課題 DFAをシミュレートするプログラム基本的には状態遷移関数を実装すればＯＫ。コンパイラなどでの字句解析では、単語（文字列）の読み込みに関してプログラミング上の工夫が必要。 Prologで書けばもっと簡単!? 状態遷移表をPrologで記述すればいいだけ！いろんな言語で実装してみてください。 OcamlやHaskellで書いても面白いですよ！（後期の授業「言語プロセッサ」で学びます。） ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（３）データ構造：・配列（またはアレイ）・リスト・スタック・キュー　などプッシュダウンオートマトン(PDA) スタックの定義スタックの構造と動作（pop-up と push-down） LIFO (Last-In First-Out) 型のメモリ PDAの定義と記述法テープ上を一方向に動くヘッド＋スタックメモリ（テープの記号を順次読み、スタック上の記号を順次読み書きしながら内部状態を遷移） M = < K, Σ, Γ,δ, q0, Z0, F > 　（７つ組）状態遷移図様相（configuration） ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（４）スタックとPDAのイメージ図 Pop up Push down LIFO (Last In First Out) 最後に入れたものが最初に取り出される。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（５）プッシュダウンオートマトン(PDA) PDAの種類決定性プッシュダウンオートマトン Deterministic pushdown automaton (DPDA) 非決定性プッシュダウンオートマトン Nondeterministic pushdown automaton (NPDA) 言語認識能力はNPDAの方が高い。 FAは正規言語（正規表現）を認識 NPDAは文脈自由言語を認識 DPDAよりもNPDAの方が言語認識能力大 ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（６）チューリングマシン(Turing Machine; TM) TMの定義と記述法テープ上を左右どちらにも動けるヘッド（テープ上の記号を順次読み、テープ上に時として記号を書き込みながら、そのたびごとに内部状態を遷移） M = < K, Γ, Σ, δ, q0, B, F > 　（７つ組）状態遷移図様相（configuration） TMの種類決定性TM（DTM）非決定性TM(NTM) 言語認識能力はどのTMでも同じ。句構造言語（句構造文法に適った文）を認識 ©Tokyo University of Technology, School of Computer Science, H.Kameda

補足有限オートマトンは記憶容量有限な装置プッシュダウンオートマトンは、記憶容量に制限のない装置（スタックは必要に応じて情報を蓄積できる）有限オートマトンは正規言語、プッシュダウンオートマトンは文脈自由言語をそれぞれ認識することができる。それ以上一般の言語の認識するにはチューリングマシンが必要。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

質問現在のコンピュータは、どの種類のオートマトンと考えることができるか？　その理由とともに答えなさい。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

質問オートマトン（の理論）が利用されている例を５つ挙げなさい。パックマンなどのゲーム gccなどのコンパイラ（言語プロセッサ）それから．．． ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（７）オートマトンと形式言語（形式文法）とは相互に密接な関係がある．したがって，形式言語も深く学ぶ価値がある．オートマトンの応用分野：計算モデル計算概念の定式化計算可能性計算量その他形式言語の応用分野：自然言語処理・音声処理カナ漢字変換システム機械翻訳システム自動通訳システムプログラミング言語とその処理コンパイラ設計プログラミング言語設計その他 ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（８）：言語の形式的定義単語ｗ： X1, X2, X3, ・・・, Xn （はじめに単語ありき）語彙V (Vocabulary) ：　単語の集合 V = { X1, X2, X3, ・・・, Xn } (有限集合) 文(sentence)：単語の並び（単語の列）（注） Vの要素( X1 や X2 など)は単語 Xa Xb Xc Xd など，単語の並びは何でも文と考える．でも何でも良いわけではない。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（９）：考察文は無限個存在する。（単語は有限個）言語L（例えば英語）として意味のあるものとそうでないものとが混ざっている。 ⇒ 言語Lとして意味のある文をすべて集めた集合は、１つの言語（今の場合はL）を定める。 ⇒ 言語Lとして意味があるものとないものとを　区別したい。つまり、任意の文（単語列）に対して、それが　言語Lの文かそうではないのかを判定したい。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

そんなことできるのだろうか？でも、人間はやっているよ！じゃあ、できるんだね！（信念）自動機械（オートマトン）を作ってみよう！ ©Tokyo University of Technology, School of Computer Science, H.Kameda

作成のためのアイデアはじめに言語Lの文すべてを知っているならば、下記のような機械ができる。 S1は言語Lの文だよ！文S1 オートマトン S1　S2　S3 … Sn ©Tokyo University of Technology, School of Computer Science, H.Kameda

問題点１でも、「言語Lの文すべてを知っている」なんて、不可能だよ！例：「２００8年6月23日、形式言語とオートマトンの授業が、講実4０3教室で、パワーポイントを用いて行われた。」　という文をあなたは事前に知っていましたか？ ©Tokyo University of Technology, School of Computer Science, H.Kameda

問題点２もし何らかの方法により、事前に言語Lのすべての文を知っていたとしても．．． Lの文の集合が無限集合のときは、このプログラムは停止しないことがある！！！ s = get_sentence(); if ( s ∈ Lの文の集合 ) then s は　Lの文である else s は　Lの文ではない end if ©Tokyo University of Technology, School of Computer Science, H.Kameda

それではどうしようか？！ ©Tokyo University of Technology, School of Computer Science, H.Kameda

ここまでのまとめ言語意味のある文（言語Lの文）の集合文法の必要性ある言語（例えば日本語）の文すべてをあらかじめ知っているなんてことは不可能！オートマトンある文が対象としている言語Lの文なのかを自動判定する装置 ©Tokyo University of Technology, School of Computer Science, H.Kameda

どうも文法が大切らしい。もう少し文法について学んでみよう！
どうも文法が大切らしい。もう少し文法について学んでみよう！ ©Tokyo University of Technology, School of Computer Science, H.Kameda

ホントにしゃべれるようになるのかなぁ普遍文法という発想すべてのヒトは、言語に依存しない普遍的な処理能力をもった装置(device)を生得的に持っており、個別言語に関する知識は後天的に獲得されるからだ。これが私の基本的考えです。僕にもこんな装置がほしいなぁ… ©Tokyo University of Technology, School of Computer Science, H.Kameda 写真の出典：Wikipediaより

その知識は、「文法」という形で獲得される。 Chomskyはそのように考えた。それでは彼の考えを見てみよう。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

文法の定義重要文法G=（ Vn, Vt, P, S ）：ただし、 Vn: 非終端記号の集合 Vt: 終端記号の集合 P: 書き換え規則の集合 S: 開始記号 ©Tokyo University of Technology, School of Computer Science, H.Kameda

文法文法G=（ Vn, Vt, P, S ）：ただし、 Vn: 非終端記号の集合　　　　　　<= 構文木構成要素の集合 Vt: 終端記号の集合 <= 単語の集合 P: 書き換え規則の集合 S: 開始記号 ©Tokyo University of Technology, School of Computer Science, H.Kameda

例１-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 } ©Tokyo University of Technology, School of Computer Science, H.Kameda

例１-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 ⑩ ©Tokyo University of Technology, School of Computer Science, H.Kameda

例１-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 ⑩ 非終端記号終端記号 ©Tokyo University of Technology, School of Computer Science, H.Kameda

例１-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 ⑩ 終端記号のみの列文 ©Tokyo University of Technology, School of Computer Science, H.Kameda

例１-2に対する問題これは木(tree)として記述せよ。この文法Gにより生成される文をすべて列挙せよ。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

言語の定義言語Lとは、文法Gにより生成されるあらゆる文の集合のこと。つまり、L＝L(G)。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

問題 Chomskyの主張が正しいとすると、日本語にも文法が存在し、それは形式文法として記述することができる。このとき、日本語は正規言語か？　そうであれば証明を、そうでなければ反例を示せ。日本語は文脈自由文法か？　そうであれば証明を、そうでなければ反例を示せ。 Chomskyの言語理論の限界は何か？ ©Tokyo University of Technology, School of Computer Science, H.Kameda

ここまでのまとめ人間の頭の中には、言語処理装置がある。すべての文を記憶しているわけではない。文法として記憶している。文法とは何か？規範文法(Prescriptive Grammar) 記述文法(Descriptive Grammar) 形式文法と形式言語 ©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 ©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 } ©Tokyo University of Technology, School of Computer Science, H.Kameda

言語の階層（重要）言語は文法の種類に応じて、階層構造をなしている。句構造言語 ⇔ 句構造文法文脈依存言語 ⇔ 文脈依存文法文脈自由言語 ⇔ 文脈自由文法正規言語 ⇔ 正規文法一般的特殊的 Chomsky階層(Chomsky Hierarchy)とも言う。 ©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) ©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) ここに制限が付くと他の文法になる。 ©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) ©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) ©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) ©Tokyo University of Technology, School of Computer Science, H.Kameda

生成規則部分の比較 PSG: α→β CSG: αXβ→αγβ CFG: X→α RG: X→aY, X→b ただし、 α，β∈V* ・γ∈V+ X, Y∈Vn ・a, b∈Vt ・V=Vn∪Vt ©Tokyo University of Technology, School of Computer Science, H.Kameda

Chomsky階層重要 PSG CSG CFG RG ©Tokyo University of Technology, School of Computer Science, H.Kameda

文法（言語）とオートマトン文　　法　　処理装置句構造文法(PSG) ⇔ ？文脈依存文法(CSG) ⇔ ？文脈自由文法(CFG) ⇔ ？正規文法(RG) ⇔ ？ ©Tokyo University of Technology, School of Computer Science, H.Kameda

文法（言語）とオートマトン文　　法　　処理装置句構造文法(PSG) ⇔ Turing 機械文脈依存文法(CSG) ⇔ 線形有界オートマトン文脈自由文法(CFG) ⇔ プッシュダウンオートマトン正規文法(RG) ⇔ 有限オートマトンこれも覚えておいてください． ©Tokyo University of Technology, School of Computer Science, H.Kameda

言語の包含関係 L（PSG) ⊃ L(CSG) ⊃ L(CFG) ⊃ L(RG) このうち、大切なのはCFGとRG。なぜ大切かというと… ©Tokyo University of Technology, School of Computer Science, H.Kameda

CFGとRG CFG（文脈自由文法）：プログラミング言語設計コンパイラの構文解析自然言語処理（機械翻訳・仮名漢字変換） RG（正規文法）：正規表現（検索・コンパイラの語彙解析） ©Tokyo University of Technology, School of Computer Science, H.Kameda

CFGの特徴 CFGには標準形がある。導出の過程を木で表現できる（導出木の存在）。解析手法が豊富に知られている。自然言語処理に部分的に適用できる。プログラミング言語設計に利用されている。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

CFGには標準形がある！これは理論的な証明を行う際に有効です！とうのは、あらゆる文脈自由文法が形式的に同じ形に書けるからです。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

１．CFGの標準形 Chomskyの標準形 Greibachの標準形教科書p.174 ©Tokyo University of Technology, School of Computer Science, H.Kameda

Chomskyの標準形どの書き換え規則も，右辺がただ一つの終端記号になっているか，２個の非終端記号だけである　という条件を満たしている．つまり，… A →　BC A →　a ただし，A,B,Cは非終端記号，aは終端記号 ©Tokyo University of Technology, School of Computer Science, H.Kameda

Greibachの標準形どの書き換え規則も，その右辺が左端にただ一つの終端記号を有し，かつ，その終端記号に続いて０個以上の非終端記号からなっている，　という条件を満たしている．つまり，… A →　a A → aB A → aBC A → aBCD … A → aBCD…E…F ただし，A～Fは非終端記号，aは終端記号 ©Tokyo University of Technology, School of Computer Science, H.Kameda

Chomskyの標準形任意のCFGにおける書き換え規則群Pは、A→BC　または　A→a　という形だけで表現できる。　 ©Tokyo University of Technology, School of Computer Science, H.Kameda

Greibachの標準形任意のCFGにおける書き換え規則群Pは、A→aα　という形だけで表現できる。ただし、X∈Vn, a∈Vt, α∈Vn*。　 ©Tokyo University of Technology, School of Computer Science, H.Kameda

Chomskyの標準形への変換方法（教科書 p.177 問題6.9）　できるようになっておいてください。試験に出るかもしれません。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

例示 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標準形文法を求めよう． ©Tokyo University of Technology, School of Computer Science, H.Kameda

結果 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 ©Tokyo University of Technology, School of Computer Science, H.Kameda

練習問題 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標準形文法を求めよ．試験に出るかも？ ©Tokyo University of Technology, School of Computer Science, H.Kameda

ここまでのまとめ言語には階層がある（Chomsky階層）正規言語（正規文法）は語句解析に深い関係がある。文脈自由言語（文脈自由文法）は構文解析に深い関係がある。文脈自由文法には標準形が存在する． ©Tokyo University of Technology, School of Computer Science, H.Kameda

その他の重要事項 ©Tokyo University of Technology, School of Computer Science, H.Kameda

定理１与えられたｃｆｇ Gによって生成される言語L(G)が，空集合かそうでないかを決定するアルゴリズムが存在する． ©Tokyo University of Technology, School of Computer Science, H.Kameda

定理２与えられたｃｆｇ Gによって生成される言語L(G)が，有限集合か無限集合かを決定するアルゴリズムが存在する．（つまり，生成される文が有限個なのか無限個なのかを決定するアルゴリズムが存在する，ということ．） ©Tokyo University of Technology, School of Computer Science, H.Kameda

定理３文法Gが自己埋め込みでないcfgであれば，L(G)は正規集合である．定義（自己埋め込み）：　どちらも空でない文字列α1，α2について　A ＝＞ α1 A α2 となるような非終端記号Aが存在すること． ©Tokyo University of Technology, School of Computer Science, H.Kameda

注 G=< { S }, { a, b }, P, S > P: S→aSa S →aS S →bS S →a S →b ©Tokyo University of Technology, School of Computer Science, H.Kameda

文法の曖昧性自己埋め込みはｃｆｇを特徴付ける性質の１つ。これとは別に、“曖昧性”というのも重要な概念です。押さえておきましょう！（注）ここでいう曖昧性とは、ambiguityです。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

文法と言語とオートマトン句構造文法(PSG) 文脈依存文法(CSG) 文脈自由文法(CFG) 正規文法(RG) ©Tokyo University of Technology, School of Computer Science, H.Kameda

言語の階層（重要）言語は文法の種類に応じて、階層構造をなしている。句構造言語 ⇔ 句構造文法文脈依存言語 ⇔ 文脈依存文法文脈自由言語 ⇔ 文脈自由文法正規言語 ⇔ 正規文法一般的特殊的 Chomsky階層(Chomsky Hierarchy)とも言う。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

文法（言語）とオートマトン文　　法　　処理装置句構造文法(PSG) ⇔ Turing 機械文脈依存文法(CSG) ⇔ 線形有界オートマトン文脈自由文法(CFG) ⇔ プッシュダウンオートマトン正規文法(RG) ⇔ 有限オートマトンこれも覚えておいてください． ©Tokyo University of Technology, School of Computer Science, H.Kameda

確認（７）オートマトンと形式言語（形式文法）とは相互に密接な関係がある．したがって，形式言語も深く学ぶ価値がある．オートマトンの応用分野：計算モデル計算概念の定式化計算可能性計算量その他形式言語の応用分野：自然言語処理・音声処理カナ漢字変換システム機械翻訳システム自動通訳システムプログラミング言語とその処理コンパイラ設計プログラミング言語設計その他 ©Tokyo University of Technology, School of Computer Science, H.Kameda

ここまでは「オートマトンと形式言語」の関係に重点をおいてきたが、もう一つの側面として、「オートマトンと計算」がある。以下はこれについて概観してみよう！最後の話題です！ ©Tokyo University of Technology, School of Computer Science, H.Kameda

Turing認識可能性と Turing決定可能性
Turing-recognizablity Turing-decidability ©Tokyo University of Technology, School of Computer Science, H.Kameda

定義：装置Mが言語Lを認識する装置Mが言語Lを認識する　 　L　＝　｛ w | Mがwを受理(accept)する　｝ ©Tokyo University of Technology, School of Computer Science, H.Kameda

定義：言語LがTuring認識可能あるTuringマシンが存在し、それが言語Lを認識するとき、言語LはTuring認識可能であるという。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

Turingマシンの動作について Turingマシンに入力を与え、動作を開始させると以下の３つの結果が生じる。その入力文字列をacceptするその入力文字列をrejectする無限ループに陥り、動作が停止しない！ ©Tokyo University of Technology, School of Computer Science, H.Kameda

定義：決定するあるTuringマシンにある言語の文を入力として与え、動作を開始させたとき、Turingマシンはやがて停止し、その入力をacceptするかrejectするとき、そのTuringマシンはその言語の決定器であるといい、また、そのTuringマシンはその言語を決定するという。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

定義：言語LがTuring決定可能あるTuringマシンが存在し、それが言語Lを決定するとき、言語LはTuring決定可能であるという。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

例：言語はTuring-decidable(Turing決定可能)な言語である。チャレンジ問題　この言語Lを受理するTuringマシンを　構成してみよう。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

アルゴリズムとは何か？ “アルゴリズム(algorithm)”という用語はもともと数学の分野で“手続き(procedure or recipe)”とも呼ばれていたもの。素数を発見するためのアルゴリズム(例：エラストテネスの篩法)や最大公約数を計算するアルゴリズム(ユークリッド互除法)などが有名である。　しかしながら、“何らかの仕事を処理するための指示群”といった程度の概念でとらえられていた。（それでも十分だった…） ©Tokyo University of Technology, School of Computer Science, H.Kameda

Hilbertの２３の問題 1900年に数学者David Hilbertがパリで開催された国際数学者会議の講演で、23の問題を提案した。その第10問題がアルゴリズムに関するものであった。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

Hilbertの第10問題多項式(polynomial)pが与えられたとき、その多項式pは整数解のみを持つ多項式であるのか否かを判定する手順（アルゴリズム）を考えよ。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

例：次の多項式pはx=5,y=3,z=0のときゼロになる。つまり、pは整数解を持つ。与えられた任意の多項式がこのように整数解のみを持つかどうかを判定する処理手続きを考案したい。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

考えてみてください！ある種の数学者たちはこのような問題に取り組んでいます！皆さんも数学者に挑戦してみては？ ©Tokyo University of Technology, School of Computer Science, H.Kameda

事実そんなアルゴリズムは存在しない！でも、存在しないことを証明することは困難であった。「存在する」という証明は、例を１つみつければOK . 「存在しない」というのはどうやって証明すればいいのか？そのような背景からアルゴリズムの理解は深まって行った。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

歴史的な話 1936年、Alonzo ChurchとAlan Turingの二人がそれぞれ“アルゴリズムの定義”を提案した。ラムダ計算(λ-clculus)による定義　（Church） Turing machineによる定義　（Turing）この２つの定義は同等であることが示された！（これをChurch-Turing Thesisという） ©Tokyo University of Technology, School of Computer Science, H.Kameda

Hilbertの第10問題次のDは決定可能(decidable)か？ D = { p | p は整数解のみを持つ多項式} この問題に対する答えは否定的であった。しかしながら、この問題はTuring認識可能であることを示すことができる。このことをもっと単純な問題で見てみよう！ ©Tokyo University of Technology, School of Computer Science, H.Kameda

簡単化された問題 D1={ p | pはｘに関する多項式で、整数のみを解として持つ} TM M1はD1を認識する。 M1：ｘに関する多項式pを入力とする。多項式pの値を、以下のxについて順次計算し、どこかでp=0となったらそのpをacceptする。 x=0, 1, -1, 2, -2, 3, -3, 4, -4, … ©Tokyo University of Technology, School of Computer Science, H.Kameda

これは認識可能であるが決定可能ではない。また、多変数への拡張は可能である。しかしながら、これらは決定可能ではないという問題点がある。だが、… ©Tokyo University of Technology, School of Computer Science, H.Kameda

この定理により、先の「簡単化された問題」は決定的であることが分かる。しかしながら、一般的な問題つまりHilbertの第10問題は決定可能なのだろうか？ ©Tokyo University of Technology, School of Computer Science, H.Kameda

1970年、Yuri MatijasevicによりHilbertの第10問題に対するアルゴリズムは存在しないことが証明された。（ Matijasevic の定理） ©Tokyo University of Technology, School of Computer Science, H.Kameda

おまけ無限と有限について整数は自然数と同じだけある（個数は同じ）。有理数は自然数と同じだけある。無理数は自然数よりもたくさんある。 ©Tokyo University of Technology, School of Computer Science, H.Kameda

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

Similar presentations

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

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

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

Similar presentations

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

Similar presentations

About project

フィードバック

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

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