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

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

©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

©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

©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

©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 セル 入力記号 入力テープ ヘッド 内部状態 ・・・ ・・・

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

©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

©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

©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

©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

©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

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

©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

©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

©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

©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

©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 それではどうしようか？！ ©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

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

©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=（ Vn, Vt, P, S ）： ただし、 Vn: 非終端記号の集合 Vt: 終端記号の集合 P: 書き換え規則の集合 S: 開始記号 ©Tokyo University of Technology, School of Computer Science, H.Kameda

©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

©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

©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

©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

©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

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

©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

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

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

©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

©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

©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

句構造文法 (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

©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

©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

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

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

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

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

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

©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

©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

©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

©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

©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

©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

©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

©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

©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

©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 その他の重要事項 ©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

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

©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

©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

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

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

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

©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

©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

©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

©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

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

©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

©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

©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

©Tokyo University of Technology, School of Computer Science, H.Kameda 定理 非決定性TMは同等な決定性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

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

©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

©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

©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 考えてみてください！ ある種の数学者たちはこのような問題に取り組んでいます！ 皆さんも数学者に挑戦してみては？ ©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

©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

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

©Tokyo University of Technology, School of Computer Science, H.Kameda 定理 多項式 　がx=aでp=0とする。このとき、 　とするとき以下の不等式が成り立つ。 ©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

©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 おまけ 無限と有限について 整数は自然数と同じだけある（個数は同じ）。 有理数は自然数と同じだけある。 無理数は自然数よりもたくさんある。 ©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