形式言語とオートマトン2011 ー第10日目ー 東京工科大学 コンピュータサイエンス学部 亀田弘之 今日も言語について理解を深めましょう。 • 言語とは何か。 • 言語とは如何に定義されるものなのか。 • 言語とは... Tokyo University of technology (Thought and Language Lab) 2 今日の内容 1. 曖昧性 2. 標準形 3. 自己埋め込み性 4. その他 • (ポンプの定理の証明) Tokyo University of technology (Thought and Language Lab) 3 1.曖昧性 • “あいまいせい”と読む。 • 曖昧性(日本語)には複数の意味がある。 • Ambiguity • Vague • Fuzzy など 形式言語で取り上げる曖昧性とは、一般 にambiguity(多義性)のことである。 Tokyo University of technology (Thought and Language Lab) 4 Tokyo University of technology (Thought and Language Lab) 5 Tokyo University of technology (Thought and Language Lab) 6 vague Tokyo University of technology (Thought and Language Lab) 7 fuzzy Tokyo University of technology (Thought and Language Lab) 8 1.曖昧性 • 構文の曖昧性 • 文法の曖昧性(曖昧な文法) • 言語の曖昧性(曖昧な言語) 例: 賢いボクの友達 美しい水車小屋の娘 青いルビーのケース Tokyo University of technology (Thought and Language Lab) 9 • 真っ赤なネギ入りのラーメン Tokyo University of technology (Thought and Language Lab) 10 前回の授業のスライド 例3 • 文法 : G=( Vn, Vt, P, S ): – ただし、 • 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) 11 前回の授業のスライド 問 (前述の例3の文法Gに対して) • a+a×a の導出木を示せ。 • (a+a)×a の導出木を示せ。 Tokyo University of technology (Thought and Language Lab) 12 前回の授業のスライド 例4 (例3のPを以下のものに変えると…) • P={ } E → E+E | E×E | ( E ) | a 曖昧な文法 (ambiguous grammar) Tokyo University of technology (Thought and Language Lab) 13 問 曖昧性は悪いこと? 良いこと? Tokyo University of technology (Thought and Language Lab) 14 2.CFGの標準形 • Chomskyの標準形 • Greibachの標準形 Tokyo University of technology (Thought and Language Lab) 15 Chomskyの標準形 • 任意のCFGにおける書き換え規則群Pは、 A→BC または A→a という形だけで表現できる。 Tokyo University of technology (Thought and Language Lab) 16 Greibachの標準形 • 任意のCFGにおける書き換え規則群Pは、 A→aα という形だけで表現できる。ただ し、X∈Vn, a∈Vt, α∈Vn*。 Tokyo University of technology (Thought and Language Lab) 17 Chomskyの標準形への変換方法 S → ASA |aB A → B|S B→b Tokyo University of technology (Thought and Language Lab) 18 Chomskyの標準形への変換方法(易しい例) S → ASA |aB B→b Tokyo University of technology (Thought and Language Lab) 19 自己埋め込み性 • CFGが自己埋め込みとは、 A → aAb となるような非終端記号Aが存在すること。 ただし、a, b は空でない記号列。 Tokyo University of technology (Thought and Language Lab) 20 ポンピングの補題 • 言語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) 21 問題(教室で配布します) • ポンピングの補題を確認する問題です。 これを通じてDFAを深く理解しましょう。 Tokyo University of technology (Thought and Language Lab) 22
© Copyright 2025 ExpyDoc