形式言語とオートマトン2016 ～第10日目(形式文法2回目)～ 東京工科大学 コンピュータサイエンス学部 亀田弘之 お知らせ：　次回平成28年6月28日（火）は、授業評価アンケートをします。

今日も“言語”について理解を深めましょう。 言語とは何か。 言語とは如何に定義されるものなのか。 言語とは．．． Tokyo University of technology (H.Kameda) 2016/June/21

今日の内容 曖昧性 標準形 自己埋め込み性 その他 (ポンプの定理の証明) Tokyo University of technology (H.Kameda) 2016/June/21

１．曖昧性 “あいまいせい”と読む。 曖昧性（日本語）には複数の意味がある。 Ambiguous Vague Fuzzy 　など 形式言語で取り上げる曖昧性とは、一般にambiguity（多義性）のことである。 Tokyo University of technology (H.Kameda) 2016/June/21

Tokyo University of technology (H.Kameda) 2016/June/21

Tokyo University of technology (H.Kameda) 2016/June/21

vague Tokyo University of technology (H.Kameda) 2016/June/21

Vagueの例： The outline of buildings is vague. Tokyo University of technology (H.Kameda) 2016/June/21

fuzzy Tokyo University of technology (H.Kameda) 2016/June/21

１．曖昧性 意味の曖昧性 構文の曖昧性 文法の曖昧性（曖昧な文法） 言語の曖昧性（曖昧な言語） Tokyo University of technology (H.Kameda) 2016/June/21

意味の曖昧性 赤い花 (red flowers) Tokyo University of technology (H.Kameda) 2016/June/21

例３：/ le pwason ki la mo~ge ier / 構文の曖昧性 例１：はしを渡ってはいけません。 橋を渡ってはいけません。 端を渡ってはいけません。 例２：真っ赤なネギ入りのラーメン 例３：/ le pwason ki la mo~ge ier / Le poisson qu’il a mangé hier 昨日彼が食べた魚 Le poisson qui l’a mangé hier 昨日それを食べた魚 Tokyo University of technology (H.Kameda) 2016/June/21

その他の例 / fakkusu okureta / 美しい水車小屋の娘 賢い僕の友達 漱石の本 教師の評価は必要だ。 ファックス 送れた？ ファックス 遅れた？ ファックス をくれた？ 美しい水車小屋の娘 賢い僕の友達 漱石の本 教師の評価は必要だ。 すべての受験生は外国語を１つ選択する。 Tokyo University of technology (H.Kameda) 2016/June/21

The shooting of hunters こうてんの場合はどうしようか？ その他の例（２） Celui qui l’aime Celui qu’il aime They are flying planes. Bank Position The shooting of hunters こうてんの場合はどうしようか？ Tokyo University of technology (H.Kameda) 2016/June/21

「漱石の本」の解釈を５つ以上見つけなさい。 今日の問題１ 「漱石の本」の解釈を５つ以上見つけなさい。 ヒント 和紙の本 和紙という素材で作られた本 和紙について書かれた本 手書きの本 ひらがなの本 冷凍保存の本 Tokyo University of technology (H.Kameda) 2016/June/21

前回の授業のスライド 数式文法の例 文法 ： G=（ Vn, Vt, P, S ）： 言語 ：L=L(G)は具体的にどうなる？ ただし、 Vn={ E, T, F } Vt={ a, +, ×, (, ) } P={ E → E + T | T , T → T× F | F , F → ( E ) | a } S={ E } 言語 ：L=L(G)は具体的にどうなる？ Tokyo University of technology (H.Kameda) 2016/June/21

前回の授業のスライド 問 （前述の例３の文法Gに対して） a+a×a の導出木を示せ。 (a+a)×a の導出木を示せ。 Tokyo University of technology (H.Kameda) 2016/June/21

P={ E → E+E | E×E | ( E ) | a } 曖昧な文法 （ambiguous grammar） 前回の授業のスライド 例（前例のPを以下のものに変えると…） P={ E → E+E | E×E | ( E ) | a } 曖昧な文法 （ambiguous grammar） Tokyo University of technology (H.Kameda) 2016/June/21

(以下の余白に、自分の意見を書いておこう！) 今日の問２ 曖昧性は悪いこと？　良いこと？ (以下の余白に、自分の意見を書いておこう！) Tokyo University of technology (H.Kameda) 2016/June/21

２．CFGの標準形 Chomskyの標準形 Greibachの標準形 (参考）教科書p.174 Tokyo University of technology (H.Kameda) 2016/June/21

任意のCFGにおける書き換え規則群Pは、 A→BC または A→a という形だけで表現できる。 Chomskyの標準形 任意のCFGにおける書き換え規則群Pは、 A→BC　または　A→a　という形だけで表現できる。　 Tokyo University of technology (H.Kameda) 2016/June/21

任意のCFGにおける書き換え規則群Pは、A→aα という形だけで表現できる。ただし、A∈Vn, a∈Vt, α∈Vn*。 Greibachの標準形 任意のCFGにおける書き換え規則群Pは、A→aα　という形だけで表現できる。ただし、A∈Vn, a∈Vt, α∈Vn*。　 Tokyo University of technology (H.Kameda) 2016/June/21

S → ASA |aB A → B|S B → b Chomskyの標準形への変換方法 Tokyo University of technology (H.Kameda) 2016/June/21

Chomskyの標準形への変換方法(易しい例) S → ASA |aB B → b Tokyo University of technology (H.Kameda) 2016/June/21

練習問題 Chomskyの標準形に書き直せ。 文G = ( {S, A, B}, {a, b}, P, S } ただし、Pは以下の通り。 S→bA A→a A→aS A→bAA B→aB B→b B→bS B→aBB Tokyo University of technology (H.Kameda) 2016/June/21

ＣFGが自己埋め込みとは、 A → aAb となるような非終端記号Aが存在すること。 ただし、a, b は空でない記号列。 自己埋め込み性(重要) ＣFGが自己埋め込みとは、 　　A → aAb となるような非終端記号Aが存在すること。 ただし、a, b は空でない記号列。 Tokyo University of technology (H.Kameda) 2016/June/21

ポンピングの補題（復習） 言語LはDFA　M により受理されるとする。 このときある定整数nが存在して、 z∊L, |z| ≧n なるzは、 z=uvw, |uv| ≦n, |v|≧1 のように分解され、かつ、 uviw ∊ L (i = 0, 1, 2, 3, …) となる。 （この補題はさまざまな定理の証明に役立つので、 　来週またこの話題に触れます。復習をしましょう。） Tokyo University of technology (H.Kameda) 2016/June/21

Pumping lemma Tokyo University of technology (H.Kameda) 2016/June/21

（注）提出の必要はないが、定期試験の 準備にもなるので必ずやっておくこと。 （なお、6月28日に念のため解説する。） 次回までの宿題 教科書174頁の【話題6.2】を読む。 教科書177頁の問題6.9を考える。 教科書244頁(6.9部分)を読み理解する。 （注）提出の必要はないが、定期試験の 　　　準備にもなるので必ずやっておくこと。 　　　（なお、6月28日に念のため解説する。） Tokyo University of technology (H.Kameda) 2016/June/21