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

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

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

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

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

問題1.1 参考例次のものは、２つの有限オートマトンM1とM2の状態遷移図である。それぞれについて以下の問に答えなさい。初期状態はどれか。最終状態はどれか。入力 aabb のときのオートマトンの状態遷移の系列はどうなるか。入力 aabb は受理されるか。空文字列εは受理されるか。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

問題1.2 参考例前述の問題1.1でのオートマトンM1とM2を形式的に記述しなさい。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

いろんなことを思い出しながら話しを聞いてください。
さて、今回も復習から！ざっと見ていきましょう．（記憶をリフレッシュしましょう。　短期記憶ではリハーサルが大切。　　（心理学・脳神経科学の知見より））いろんなことを思い出しながら話しを聞いてください。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

確認(1) 有限オートマトン(FA) FAの定義と記述法テープ上を一方向に動くヘッド（テープ上の記号を順次読みながら内部状態を遷移） M = <K, Σ, δ, q0, F> 　（５つ組）状態遷移図様相（configuration） FAの種類決定性FA（DFA）非決定性FA（ε遷移のあるものとないもの）言語認識能力はどのFAでも同じ。正規言語（正規表現）を認識 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

有限オートマトンのイメージ FAの概観入力記号セル a1 a2 ai-1 ai an ・・・・・・・・・ qk 入力テープヘッド内部状態 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

M1の状態遷移図参考例状態入力 a 入力 b i 1 ー 2 3 f i １２ｆ３ a b © 東京工科大学亀田弘之

確認（２）正規表現を認識するFAの存在とその構成法正規表現αが与えられる。正規表現αに対して、ε-NFA を構成する。 ε-NFA をDFAに書き換える。 DFAを状態数最少のDFA(Min-DFA)に書き換える。 Min-DFAをシミュレートするプログラムを作成する。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

研究課題 DFAをシミュレートするプログラム基本的には状態遷移関数を実装すればＯＫ。コンパイラなどでの字句解析では、単語（文字列）の読み込みに関してプログラミング上の工夫が必要。 Prologで書けばもっと簡単!? 状態遷移表をPrologで記述すればいいだけ！いろんな言語で実装してみてください。 OcamlやHaskellで書いても面白いですよ！（後期の授業「言語プロセッサ」で学びます。） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

確認（３）データ構造：・配列（またはアレイ）・リスト・スタック・キュー　などプッシュダウンオートマトン(PDA) スタックの定義スタックの構造と動作（pop-up と push-down） LIFO (Last-In First-Out) 型のメモリ PDAの定義と記述法テープ上を一方向に動くヘッド＋スタックメモリ（テープの記号を順次読み、スタック上の記号を順次読み書きしながら内部状態を遷移） M = < K, Σ, Γ,δ, q0, Z0, F > 　（７つ組）状態遷移図様相（configuration） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

確認（４）スタックとPDAのイメージ図 Pop up Push down LIFO (Last In First Out) 最後に入れたものが最初に取り出される。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

確認（５）プッシュダウンオートマトン(PDA) PDAの種類決定性プッシュダウンオートマトン Deterministic pushdown automaton (DPDA) 非決定性プッシュダウンオートマトン Nondeterministic pushdown automaton (NPDA) 言語認識能力はNPDAの方が高い。 FAは正規言語（正規表現）を認識 NPDAは文脈自由言語を認識 DPDAよりもNPDAの方が言語認識能力大 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

δ：状態遷移関数参考例 K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 ) 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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 ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 ) 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

動作のトレース参考例 (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 ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 ) 受理拒否 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

状態遷移図参考例 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

動作のトレース参考例自分で確認しよう K×(Σ∪{ε})×Γ K×Γ* δ( q0, a, Z0 ) ( q0, AZ0 ) δ( q0, a, A ) ( q0, AA ) δ( q0, b, A ) ( q1, ε ) δ( q1, b, A ) δ( q1, ε, Z0 ) ( q2, Z0 ) (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) 受理拒否 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

確認（６）チューリングマシン(Turing Machine; TM) TMの定義と記述法テープ上を左右どちらにも動けるヘッド（テープ上の記号を順次読み、テープ上に時として記号を書き込みながら、そのたびごとに内部状態を遷移） M = < K, Γ, Σ, δ, q0, B, F > 　（７つ組）状態遷移図様相（configuration） TMの種類決定性TM（DTM）非決定性TM(NTM) 言語認識能力はどのTMでも同じ。句構造言語（句構造文法に適った文）を認識 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

参考例例4.3（教科書p.96） 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

補足有限オートマトンは記憶容量有限な装置プッシュダウンオートマトンは、記憶容量に制限のない装置（スタックは必要に応じて情報を蓄積できる）有限オートマトンは正規言語、プッシュダウンオートマトンは文脈自由言語をそれぞれ認識することができる。それ以上一般の言語の認識するにはチューリングマシンが必要。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

質問現在のコンピュータは、どの種類のオートマトンと考えることができるか？　その理由とともに答えなさい。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

質問オートマトン（の理論）が利用されている例を５つ挙げなさい。パックマンなどのゲーム gccなどのコンパイラ（言語プロセッサ）それから．．． 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

確認（８）：言語の形式的定義単語ｗ： X1, X2, X3, ・・・, Xn （はじめに単語ありき）語彙V (Vocabulary) ：　単語の集合 V = { X1, X2, X3, ・・・, Xn } (有限集合) 文(sentence)：単語の並び（単語の列）（注） Vの要素( X1 や X2 など)は単語 Xa Xb Xc Xd など，単語の並びは何でも文と考える．でも何でも良いわけではない。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

確認（９）：考察文は無限個存在する。（単語は有限個）言語L（例えば英語）として意味のあるものとそうでないものとが混ざっている。 ⇒ 言語Lとして意味のある文をすべて集めた集合は、１つの言語（今の場合はL）を定める。 ⇒ 言語Lとして意味があるものとないものとを　区別したい。つまり、任意の文（単語列）に対して、それが　言語Lの文かそうではないのかを判定したい。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

そんなことできるのだろうか？でも、人間はやっているよ！じゃあ、できるんだね！（信念）自動機械（オートマトン）を作ってみよう！ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

作成のためのアイデアはじめに言語Lの文すべてを知っているならば、下記のような機械ができる。 S1は言語Lの文だよ！文S1 オートマトン S1　S2　S3 … Sn 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

問題点１でも、「言語Lの文すべてを知っている」なんて、不可能だよ！例：「２００8年6月23日、形式言語とオートマトンの授業が、講実4０3教室で、パワーポイントを用いて行われた。」　という文をあなたは事前に知っていましたか？ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

問題点２もし何らかの方法により、事前に言語Lのすべての文を知っていたとしても．．． Lの文の集合が無限集合のときは、このプログラムは停止しないことがある！！！ s = get_sentence(); if ( s ∈ Lの文の集合 ) then s は　Lの文である else s は　Lの文ではない end if 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

それではどうしようか？！ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

ここまでのまとめ言語意味のある文（言語Lの文）の集合文法の必要性ある言語（例えば日本語）の文すべてをあらかじめ知っているなんてことは不可能！オートマトンある文が対象としている言語Lの文なのかを自動判定する装置 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

どうも文法が大切らしい。もう少し文法について学んでみよう！
どうも文法が大切らしい。もう少し文法について学んでみよう！ 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

ホントにしゃべれるようになるのかなぁ普遍文法という発想すべてのヒトは、言語に依存しない普遍的な処理能力をもった装置(device)を生得的に持っており、個別言語に関する知識は後天的に獲得されるからだ。これが私の基本的考えです。僕にもこんな装置がほしいなぁ… 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部写真の出典：Wikipediaより

その知識は、「文法」という形で獲得される。 Chomskyはそのように考えた。それでは彼の考えを見てみよう。 2016年度　オートマトンと形式言語　東京工科大学コンピュータサイエンス学部

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: