形式言語とオートマトン2017 ～第10日目(形式文法2回目)～

Presentation on theme: "形式言語とオートマトン2017 ～第10日目(形式文法2回目)～"— Presentation transcript:

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

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

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

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

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

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

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

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

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

10 （参考）騙し絵 Tokyo University of technology (H.Kameda) 2016/June/21

11 （参考）騙し絵 #2 Tokyo University of technology (H.Kameda) 2016/June/21

12 （参考）騙し絵 #3 Tokyo University of technology (H.Kameda) 2016/June/21

13 われわれ人間は、いったい何を見ているのだろうか？
感想 われわれ人間は、いったい何を見ているのだろうか？ Tokyo University of technology (H.Kameda) 2016/June/21

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

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

16 例３：/ 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

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

18 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

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

20 前回の授業のスライド 数式文法の例 文法 ： 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

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

22 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

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

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

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

26 任意の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

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

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

29 練習問題 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

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

31 ポンピングの補題（復習） 言語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

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

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