形式言語とオートマトン2011
ー第9日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
今日から
形式言語の
話です!
Copyright© 2011 School of Computer Science, Tokyo University of Technology
形式文法と形式言語
• 形式文法(formal grammars)
• 形式言語(formal languages)
2
Copyright© 2011 School of Computer Science, Tokyo University of Technology
形式言語とオートマトン
Formal Languages and Automata
平成23年度開講科目
第2部
以前使ったパワーポイントをあらた
めて詳しく理解しましょう。
文法とは?

その言語を使用する人たちが皆で守り従わな
ければならない言語に関する規則の総体。
4
Copyright© 2011 School of Computer Science, Tokyo University of Technology
文法は「言語政策」・「言語教育」のために
重要。
 現在使われている日本語に関する言語規則
はどうなっているのか?
 このような観点から本授業では文法を考える。
 文法は、機械翻訳・電話通訳さらにはデータ
マイニング(Webマイニング,評判分析)さらに
は要求工学等の分野でも極めて重要である。

5
Copyright© 2011 School of Computer Science, Tokyo University of Technology



さらにもう一歩考えをすすめて...
「あらゆる言語に共通の言語規則はある
の?」と考えるのが、「一般普遍文法
(universal grammar)」である。
これについて、少し詳しく話すと...
6
Copyright© 2011 School of Computer Science, Tokyo University of Technology
例えば、“これは何?”の答え
これは本です。
 This is a book.
 Das ist ein Buch.
 C’est un livre.
 Ειναι ενα βιβλιο.
 这是一本书。
 Ini buku.

(英語)
(独語)
(仏語)
(希語)
(中国語)
(マレー語)
7
Copyright© 2011 School of Computer Science, Tokyo University of Technology
一般普遍文法(1)
前述のオートマトンの説明を思い起こすと…
 すべての子供はやがて言葉を話しはじめる。
 日本人のこどもも、エスキモーのこどもも、
エジプトのこどもも…
 人種・民族にかかわらず話し始める。
 でも、日本人は日本語、エスキモー人はエス
キモー語をしゃべり始める。Why?

8
Copyright© 2011 School of Computer Science, Tokyo University of Technology
Because…

その言語をしゃべる環境で育ったから?

環境が習得言語を決める?

でも、なぜ基本的に人は皆しゃべり始めるの?
ミミズはしゃべらないのに?(ホント?)

それは、...

9
Copyright© 2011 School of Computer Science, Tokyo University of Technology
ホントにしゃべれるよ
うになるのかなぁ

すべてのヒトは、
言語に依存しない普遍的な処理能力をもった
装置(device)を生得的に持っており、
 個別言語に関する知識は後天的に獲得されるか
らだ。

僕にもこん
な装置がほ
しいなぁ…
これが私の
基本的考えです。
10
Copyright© 2011 School of Computer Science, Tokyo University of Technology

その知識は、「文法」という形で獲得される。

Chomskyはそのように考えた。

それでは彼の考えを見てみよう。
11
Copyright© 2011 School of Computer Science, Tokyo University of Technology
ここからが大切
(注)言語認識装置としてのオートマトンを知っ
ているとの立場で、さらに言語・文法について
理解を深めましょう!
12
Copyright© 2010 School of Computer Science, Tokyo University of Technology
文法の定義

文法G=( Vn, Vt, P, S ):

ただし、




Vn:
Vt:
P:
S:
非終端記号の集合
終端記号の集合
書き換え規則の集合
開始記号
13
Copyright© 2011 School of Computer Science, Tokyo University of Technology
文法

文法G=( Vn, Vt, P, S ):

ただし、




Vn:
Vt:
P:
S:
非終端記号の集合 <= 構文木構成要素の集合
終端記号の集合
<= 単語の集合
書き換え規則の集合
開始記号
14
Copyright© 2011 School of Computer Science, Tokyo University of Technology
例1-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 }

15
Copyright© 2011 School of Computer Science, Tokyo University of Technology
言語の定義


言語Lとは、文法Gにより生成される
あらゆる文の集合のこと。
つまり、L=L(G)。
16
Copyright© 2011 School of Computer Science, Tokyo University of Technology
文法の分類
文法にはいくつかの種類がある。
 それに応じて、処理装置・処理方法が
異なってくる。

17
Copyright© 2011 School of Computer Science, Tokyo University of Technology
ここまでのまとめ
• 文法 : G=( Vn, Vt, P, S ):
– ただし、
•
•
•
•
Vn:
Vt:
P:
S:
非終端記号の集合 <= 構文木構成要素の集合
終端記号の集合
<= 単語の集合
書き換え規則の集合
開始記号
• 言語 :L=L(G)
18
Copyright© 2010 School of Computer Science, Tokyo University of Technology
例1
19
Copyright© 2010 School of Computer Science, Tokyo University of Technology
例1
• 文法 : G=( Vn, Vt, P, S ):
– ただし、
•
•
•
•
Vn={ A, B }
Vt={ 0, 1, # }
P={ A→0A1, A →B, B →# }
S={ A }
• 言語 :L=L(G)は具体的にどうなる?
20
Copyright© 2010 School of Computer Science, Tokyo University of Technology
A ⇒ 0A1 ⇒00A11 ⇒000A111 ⇒ 000B111 ⇒
000#111
21
Copyright© 2010 School of Computer Science, Tokyo University of Technology
例2
• 文法 : G=( Vn, Vt, P, S ):
– ただし、
• Vn={ 文, 名詞句, 動詞句, 複合名詞, 複合動詞,
前置詞句, 前置詞, 冠詞, 名詞, 動詞}
• Vt={ a, the, boy, girl, flower, touches, likes, sees,
with }
• P:次のページ参照
• S={ 文 }
• 言語 :L=L(G)は具体的にどうなる?
22
Copyright© 2010 School of Computer Science, Tokyo University of Technology
• P={
文→ 名詞句 動詞句
名詞句→ 複合名詞|複合名詞 前置詞句
動詞句→ 複合動詞|複合動詞 前置詞句
前置詞句→ 前置詞 複合名詞
複合名詞→ 冠詞 名詞
複合動詞→ 動詞|動詞 名詞句
冠詞→ a|the
名詞→ boy|girl|flower
動詞→ touches|likes|sees
前置詞→ with
}
23
Copyright© 2010 School of Computer Science, Tokyo University of Technology
言語の構成要素(=文)の例
• a boy sees
• the boy sees a flower
• a girl with a flower likes the boy
など
問:これらの導出過程を示せ。
文⇒名詞句 動詞句
⇒…
24
Copyright© 2010 School of Computer Science, Tokyo University of Technology
例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)は具体的にどうなる?
25
Copyright© 2010 School of Computer Science, Tokyo University of Technology
問
• a+a×a の導出木を示せ。
• (a+a)×a の導出木を示せ。
26
Copyright© 2010 School of Computer Science, Tokyo University of Technology
例4
• P={
E → E+E | E×E | ( E ) | a
}
曖昧な文法
27
Copyright© 2010 School of Computer Science, Tokyo University of Technology
きょうはここまで...
• 言語というと、日本語・英語といったものを考
えがちですが、JavaやCも(形式)言語です。
28
Copyright© 2010 School of Computer Science, Tokyo University of Technology
ダウンロード

配布資料 ppt