東京工科大学 コンピュータサイエンス学部 亀田弘之 形式言語とオートマトン2013 ー第11日目ー 東京工科大学 コンピュータサイエンス学部 亀田弘之 今日は授業評価アンケートを実施します。

今日も言語について理解を深めましょう。 言語とは何か。 言語とは如何に定義されるものなのか。 言語とは．．． Tokyo University of technology (Thought and Language Lab)

今日の内容 曖昧性 標準形 自己埋め込み性 その他 (ポンプの定理の証明) Tokyo University of technology (Thought and Language Lab)

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

Tokyo University of technology (Thought and Language Lab)

Tokyo University of technology (Thought and Language Lab)

vague Tokyo University of technology (Thought and Language Lab)

Vagueの例： The outline of buildings is vague. Tokyo University of technology (Thought and Language Lab)

fuzzy Tokyo University of technology (Thought and Language Lab)

１．曖昧性 意味の曖昧性 構文の曖昧性 文法の曖昧性（曖昧な文法） 言語の曖昧性（曖昧な言語） Tokyo University of technology (Thought and Language Lab)

意味の曖昧性 赤い花 (red flower) Tokyo University of technology (Thought and Language Lab)

例３：/ 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 (Thought and Language Lab)

その他の例 / fakkusu okureta / 美しい水車小屋の娘 賢い僕の友達 漱石の本 ファックス 送れた？ ファックス 遅れた？ ファックス をくれた？ 美しい水車小屋の娘 賢い僕の友達 漱石の本 Tokyo University of technology (Thought and Language Lab)

「漱石の本」の解釈を２つ以上見つけなさい。 今日の問題１ 「漱石の本」の解釈を２つ以上見つけなさい。 Tokyo University of technology (Thought and Language Lab)

前回の授業のスライド 数式文法の例 文法 ： 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 (Thought and Language Lab)

前回の授業のスライド 問 （前述の例３の文法Gに対して） a+a×a の導出木を示せ。 (a+a)×a の導出木を示せ。 Tokyo University of technology (Thought and Language Lab)

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 (Thought and Language Lab)

今日の問２ 曖昧性は悪いこと？　良いこと？ Tokyo University of technology (Thought and Language Lab)

２．CFGの標準形 Chomskyの標準形 Greibachの標準形 (参考）教科書p.174 Tokyo University of technology (Thought and Language Lab)

任意のCFGにおける書き換え規則群Pは、 A→BC または A→a という形だけで表現できる。 Chomskyの標準形 任意のCFGにおける書き換え規則群Pは、 A→BC　または　A→a　という形だけで表現できる。　 Tokyo University of technology (Thought and Language Lab)

任意のCFGにおける書き換え規則群Pは、A→aα という形だけで表現できる。ただし、X∈Vn, a∈Vt, α∈Vn*。 Greibachの標準形 任意のCFGにおける書き換え規則群Pは、A→aα　という形だけで表現できる。ただし、X∈Vn, a∈Vt, α∈Vn*。　 Tokyo University of technology (Thought and Language Lab)

S → ASA |aB A → B|S B → b Chomskyの標準形への変換方法 Tokyo University of technology (Thought and Language Lab)

Chomskyの標準形への変換方法(易しい例) S → ASA |aB B → b Tokyo University of technology (Thought and Language Lab)

練習問題 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 (Thought and Language Lab)

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

ポンピングの補題（復習） 言語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 (Thought and Language Lab)

Pumping lemma Tokyo University of technology (Thought and Language Lab)