東京工科大学 コンピュータサイエンス学部 亀田弘之

Presentation on theme: "東京工科大学 コンピュータサイエンス学部 亀田弘之"— Presentation transcript:

1 東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2016 ー第9日目ー 今日からは 形式言語の話をします！ 東京工科大学 コンピュータサイエンス学部 亀田弘之 後半戦も 頑張るぞ！

2 お知らせ ・8月2日（火）は定期試験（要掲示で確認）

3 形式文法と形式言語 形式文法（formal grammars） 形式言語（formal languages）
2013年のbaccalauréat（フランスの国家資格の１つで，大学入学のためのもの）の哲学の試験問題です。 　　問：「言語は道具でしかないのか？ 　　　　（“Le langage n‘est-il qu’un outil ?”）」。 皆さんならどう解答しますか？

4 形式言語とオートマトン Formal Languages and Automata
第１回目の授業資料（一部改編） 形式言語とオートマトン Formal Languages and Automata

5 文法とは？ その言語を使用する人たちが皆で守り従わなければならない言語に関する規則の総体。 ・文法, grammar

6 もう少し細かく見ると．．． 文法は言語政策や言語教育のために重要。 現在使われている日本語に関する言語規則はどうなっているのか？
文法は、機械翻訳，電話通訳，データマイニング(Webマイニング，評判分析等），さらには要求工学等の分野でも極めて重要である。 文法という用語は、いろんな分野で使われている。重要なんだろうなぁ。

7 さらに一歩考えを進めて．．． 「あらゆる言語に共通な言語規則はあるのか？　 そう、あるんだ！」と考えるのが、 「一般普遍文法（universal grammar）」である。 これについて、少し詳しく話すと．．．

8 地球上にはさまざまな人たちが 住んでいます。
多様な気候 多様な歴史 多様な文化 多様な地形 多様な思い 多様な言語 多様な風土

9 地球上にはさまざまな人たちが 住んでいます。
多様な気候 多様な歴史 多様な中にも普遍性あり 多様な文化 多様な地形 多様な思い 多様な言語 多様な風土

10 コメント（留学生の皆さんへ） 普遍 不変 不偏 この3つの単語は、読みは同じですが意味が違います（同音異義語）。気を付けましょう！

11 例えば、“これは何？”の答え これは本です。 （日本語） This is a book. (英語)
これは本です。　　 （日本語） This is a book. (英語) Das ist ein Buch. （独語） C’est un livre. （仏語） Ειναι ενα βιβλιο. （ギリシア語） 这是一本书。 （中国語） Ini buku. （マレー語） Это книга.　　　　　 （ロシア語） هذا هو الكتاب （アラビア語） <= correct?

12 例えば、“これは何？”の答え 共通性何か見つかった？ これは本です。 （日本語） This is a book. (英語)
これは本です。　　 （日本語） This is a book. (英語) Das ist ein Buch. （独語） C’est un livre. （仏語） Ειναι ενα βιβλιο. （ギリシア語） 这是一本书。 （中国語） Ini buku. （マレー語） Это книга.　　　　　 （ロシア語） هذا هو الكتاب （アラビア語） <= correct? 共通性何か見つかった？

13 一般普遍文法（１） すべての子供はやがて言葉を話し始める。 日本人の子供も、エスキモーの子供も、 サウジアラビアの子供も…
人種・民族にかかわらず話し始める。 でも、日本人は日本語、エスキモー人はエスキモー語をしゃべり始める。Why?

14 Because… その言語をしゃべる環境で育ったから？ 環境が習得言語を決める？ でも、なぜ基本的に人は皆しゃべり始めるの？
ミミズはしゃべらないのに？（ホント？） それは、．．． （参考図書）“Animal Nature and Human Nature,” William Homan Thorpe　(1974).

15 すべてのヒトは、 言語に依存しない普遍的な処理能力をもった 装置(device)を生得的に持っており、
ホントにしゃべれるようになるのかなぁ すべてのヒトは、 言語に依存しない普遍的な処理能力をもった 装置(device)を生得的に持っており、 個別言語に関する知識は後天的に獲得されるからだ。 これが私の 基本的考えです。 僕にもこんな装置がほしいなぁ…

16 その知識は、「文法」という形で獲得される。
Chomskyはそのように考えた。 それでは彼の考えを見てみよう。

17 ここからが大切 （注）言語認識装置としてのオートマトンを知っているとの立場で、さらに言語・文法について理解を深めよう！
この授業を受けている皆さんは、 オートマトンをもう知っていますよね。

18 文法とは Grammar, that is … 文法の本質に迫っていきましょう！

19 文法の定義 文法G=（ Vn, Vt, P, S ）： ただし、 Vn: 非終端記号の集合 Vt: 終端記号の集合 P: 書き換え規則の集合

20 文法 文法G=（ Vn, Vt, P, S ）： ただし、 Vn: 非終端記号の集合 <= 構文木構成要素の集合

21 例１-1 G=(Vn, Vt, P, S) Vn = { S, NPs, NPo, VP, PN, DET, N, V }
Vt = { I, You, have, throw, a, the, book, ball } P = { ①：S → NPs VP, ②：NPs → PN, ③：PN → I, ④：PN → You, ⑤：NPo → DET N, ⑥：VP → V NPo, ⑦：DET → a, ⑧：DET → the, ⑨：N → book, ⑩：N → ball, ⑪：V → have, ⑫：V → throw }

22 言語の定義（その２） 言語Lとは、文法Gにより生成される あらゆる文の集合のこと。 つまり、L＝L(G)。

23 文法の分類 文法にはいくつかの種類がある。 それに応じて、処理装置・処理方法が 異なってくる。

24 ここまでのまとめ 文法 ： G=（ Vn, Vt, P, S ）： 言語 ：L=L(G) ただし、

25 例１ （オートマトンの時にも言いましたが、抽象的な話は、具体例を通じて理解するのがコツです。）

26 例１（続き） 文法 ： G=（ Vn, Vt, P, S ）： 言語 ：L=L(G)は具体的にどうなる？ ただし、 Vn={ A, B }
P={ A→0A1, A →B, B →# } S={ A } 言語 ：L=L(G)は具体的にどうなる？

27 A ⇒ 0A1 ⇒00A11 ⇒000A111 ⇒ 000B111 ⇒ 000#111 練習： この文法から生成される文を５つ以上、求めてみよう。

28 例2 文法 ： G=（ Vn, Vt, P, S ）： 言語 ：L=L(G)は具体的にどうなる？ ただし、
Vt={ a, the, boy, girl, flower, touches, likes, sees, with } P：次のページ参照 S={ 文 } 言語 ：L=L(G)は具体的にどうなる？

29 P={ 文→ 名詞句　動詞句 名詞句→ 複合名詞｜複合名詞　前置詞句 動詞句→ 複合動詞｜複合動詞　前置詞句 前置詞句→ 前置詞　複合名詞 複合名詞→ 冠詞　名詞 複合動詞→ 動詞｜動詞　名詞句 冠詞→ a | the 名詞→ boy | girl | flower 動詞→ touches | likes | sees 前置詞→ with }

30 言語の構成要素(=文)の例 a boy sees the boy sees a flower
a girl with a flower likes the boy など 問：これらの導出過程を示せ。 　　　文⇒名詞句　動詞句 　　　　 ⇒ …

31 例3 文法 ： 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)は具体的にどうなる？

32 問 a+a×a　の導出木を示せ。 (a+a)×a の導出木を示せ。

33 例４ P={ E → E+E | E×E | ( E ) | a } 曖昧な文法

34 文法の話、 今日はここまでとしましょう。 言語というと、日本語・英語といったものを考えがちですが、JavaやCも（形式）言語です。

35 おまけの話

36 ポンピングの補題（再） 言語 L は DFA　M により受理されるとする。このときある定整数 n が存在して，z∊L， |z| ≧n なる z は，z=uvw， |uv| ≦n， |v|≧1 のように 分解され，かつ，uviw ∊ L となる。 （この補題は様々な証明等で役立ちます。 　大学院へ進みたい人は押さえること！）