Download presentation
Presentation is loading. Please wait.
1
形式言語とオートマトン2016 ～第10日目(形式文法2回目)～
東京工科大学 コンピュータサイエンス学部 亀田弘之 お知らせ： 次回平成28年6月28日（火）は、授業評価アンケートをします。
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
意味の曖昧性 赤い花 (red flowers)
Tokyo University of technology (H.Kameda) 2016/June/21
12
例３：/ 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
13
その他の例 / fakkusu okureta / 美しい水車小屋の娘 賢い僕の友達 漱石の本 教師の評価は必要だ。
ファックス 送れた？ ファックス 遅れた？ ファックス をくれた？ 美しい水車小屋の娘 賢い僕の友達 漱石の本 教師の評価は必要だ。 すべての受験生は外国語を１つ選択する。 Tokyo University of technology (H.Kameda) 2016/June/21
14
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
15
「漱石の本」の解釈を５つ以上見つけなさい。
今日の問題１ 「漱石の本」の解釈を５つ以上見つけなさい。 ヒント 和紙の本 和紙という素材で作られた本 和紙について書かれた本 手書きの本 ひらがなの本 冷凍保存の本 Tokyo University of technology (H.Kameda) 2016/June/21
16
前回の授業のスライド 数式文法の例 文法 ： 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
17
前回の授業のスライド 問 （前述の例３の文法Gに対して） a+a×a の導出木を示せ。 (a+a)×a の導出木を示せ。
Tokyo University of technology (H.Kameda) 2016/June/21
18
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
19
(以下の余白に、自分の意見を書いておこう！)
今日の問２ 曖昧性は悪いこと？ 良いこと？ (以下の余白に、自分の意見を書いておこう！) Tokyo University of technology (H.Kameda) 2016/June/21
20
２．CFGの標準形 Chomskyの標準形 Greibachの標準形 (参考）教科書p.174
Tokyo University of technology (H.Kameda) 2016/June/21
21
任意のCFGにおける書き換え規則群Pは、 A→BC または A→a という形だけで表現できる。
Chomskyの標準形 任意のCFGにおける書き換え規則群Pは、 A→BC または A→a という形だけで表現できる。 Tokyo University of technology (H.Kameda) 2016/June/21
22
任意の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
23
S → ASA |aB A → B|S B → b Chomskyの標準形への変換方法
Tokyo University of technology (H.Kameda) 2016/June/21
24
Chomskyの標準形への変換方法(易しい例)
S → ASA |aB B → b Tokyo University of technology (H.Kameda) 2016/June/21
25
練習問題 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
26
ＣFGが自己埋め込みとは、 A → aAb となるような非終端記号Aが存在すること。 ただし、a, b は空でない記号列。
自己埋め込み性(重要) ＣFGが自己埋め込みとは、 A → aAb となるような非終端記号Aが存在すること。 ただし、a, b は空でない記号列。 Tokyo University of technology (H.Kameda) 2016/June/21
27
ポンピングの補題（復習） 言語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
28
Pumping lemma Tokyo University of technology (H.Kameda) 2016/June/21
29
（注）提出の必要はないが、定期試験の 準備にもなるので必ずやっておくこと。 （なお、6月28日に念のため解説する。）
次回までの宿題 教科書174頁の【話題6.2】を読む。 教科書177頁の問題6.9を考える。 教科書244頁(6.9部分)を読み理解する。 （注）提出の必要はないが、定期試験の 準備にもなるので必ずやっておくこと。 （なお、6月28日に念のため解説する。） Tokyo University of technology (H.Kameda) 2016/June/21
Similar presentations
