東京工科大学 コンピュータサイエンス学部 亀田弘之 形式言語とオートマトン2011 ー第9日目ー 今日から 形式言語の話です！ 東京工科大学 コンピュータサイエンス学部 亀田弘之

形式文法と形式言語 形式文法（formal grammars） 形式言語（formal languages）

形式言語とオートマトン Formal Languages and Automata 平成23年度開講科目 第２部 以前使ったパワーポイントをあらためて詳しく理解しましょう。

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

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

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

例えば、“これは何？”の答え これは本です。 This is a book. (英語) Das ist ein Buch. （独語） C’est un livre. （仏語） Ειναι ενα βιβλιο. （希語） 这是一本书。 （中国語） Ini buku. （マレー語）

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

Because… その言語をしゃべる環境で育ったから？ 環境が習得言語を決める？ でも、なぜ基本的に人は皆しゃべり始めるの？ ミミズはしゃべらないのに？（ホント？） それは、．．．

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

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

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

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

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

例１-1 G=(Vn, Vt, P, S) Vn = { S, NPs, NPo, VP, PN, DET, N } 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 }

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

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

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

例１

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

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

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

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

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

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

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

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

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