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

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

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

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

3 形式言語とオートマトン Formal Languages and Automata
平成25年度開講科目 第2部 以前使ったパワーポイントです。 今度は詳細にわたり理解しましょう。

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

5 もう少し細かく見ると．．． 文法は「言語政策」・「言語教育」のために 重要。 現在使われている日本語に関する言語規則はどうなっているのか？
このような観点から本授業では文法を考える。 文法は、機械翻訳，電話通訳，データマイニング(Webマイニング，評判分析等），さらには要求工学等の分野でも極めて重要である。

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

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

8 一般普遍文法（１） オートマトンの説明を思い起こすと… すべての子供はやがて言葉を話しはじめる。 日本人のこどもも、エスキモーのこどもも、
サウジアラビアのこどもも… 人種・民族にかかわらず話し始める。 でも、日本人は日本語、エスキモー人はエスキモー語をしゃべり始める。Why?

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

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

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

12 ここからが大切 （注）言語認識装置としてのオートマトンを知っているとの立場で、さらに言語・文法について理解を深めよう！

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

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

15 例１-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 }

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

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

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

19 例１ （抽象的な話は、具体例を通じて理解するのがコツです。）

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

21 A ⇒ 0A1 ⇒00A11 ⇒000A111 ⇒ 000B111 ⇒ 000#111

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

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

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

25 例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)は具体的にどうなる？

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

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

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

29 今日の課題 同値関係が満たすべき性質は３つある。 次のどれか？ ①反射性( ) ②対称性（ ） ③推移性（ ） ④継承性 ⑤準同型性（ ）