Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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 1.曖昧性 “あいまいせい”と読む。 曖昧性(日本語)には複数の意味がある。 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 1.曖昧性 意味の曖昧性 構文の曖昧性 文法の曖昧性(曖昧な文法) 言語の曖昧性(曖昧な言語)
Tokyo University of technology (H.Kameda) 2016/June/21

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

16 例3:/ le pwason ki la mo~ge ier /
構文の曖昧性 例1:はしを渡ってはいけません。 橋を渡ってはいけません。 端を渡ってはいけません。 例2:真っ赤なネギ入りのラーメン 例3:/ 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 / 美しい水車小屋の娘 賢い僕の友達 漱石の本 教師の評価は必要だ。
ファックス 送れた? ファックス 遅れた? ファックス を呉れた? 美しい水車小屋の娘 賢い僕の友達 漱石の本 教師の評価は必要だ。 すべての受験生は外国語を1つ選択する。 Tokyo University of technology (H.Kameda) 2016/June/21

18 The shooting of hunters こうてんの場合はどうしようか?
その他の例(2) 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 「漱石の本」の解釈を5つ以上見つけなさい。
今日の問題1 「漱石の本」の解釈を5つ以上見つけなさい。 ヒント 和紙の本 和紙という素材で作られた本 和紙について書かれた本 手書きの本 ひらがなの本 冷凍保存の本 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 前回の授業のスライド 問 (前述の例3の文法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 (以下の余白に、自分の意見を書いておこう!)
今日の問2 曖昧性は悪いこと? 良いこと? (以下の余白に、自分の意見を書いておこう!) Tokyo University of technology (H.Kameda) 2016/June/21

24 2.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 CFGが自己埋め込みとは、 A → aAb となるような非終端記号Aが存在すること。 ただし、a, b は空でない記号列。
自己埋め込み性(重要) CFGが自己埋め込みとは、   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


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

Similar presentations


Ads by Google