study

形式言語とは?

Chomsky 形式文法、形式言語

• 自然言語の文法理論(統計・定量的)から、定性的な数学モデルを提案
• 言語:文字列集合としての見方から単語を最小単位として考え これらを抽象的な記号で表す

そもそも言語とはなにか? オートマトンとは何か?

オートマトンとは
• Automaton (pl. automata)
• Αυτοματον(ギリシア語)
(pl. Αυτοματα)
• 一般的な意味:自動機械

一般化
• 単語の一般化
I ⇔x1, have ⇔x2, a ⇔ x3, book ⇔ x4, . ⇔ x5, ・・・, kanete ⇔ xn-1, ;⇔ xn

言語の形式的定義
• 単語w: X1, X2, X3, ・・・, Xn (はじめに単語ありき)
• 語彙V (Vocabulary) : 単語の集合
V = { X1, X2, X3, ・・・, Xn } (有限集合)
• 文(sentence): 単語の並び(単語の列)
(注)
• Vの要素( X1 や X2 など)は単語
• S1 = Xa Xb Xc Xd など
• でも何でも良いわけではない。


• 語彙V={ birds, fly }
• 文:={
birds, fly,
birds birds, birds fly, fly birds, fly fly, birds birds birds, birds birds fly, birds fly birds, fly birds birds,
birds fly fly, fly birds fly, fly fly birds, …}
(無限個存在する!)

考察
• 文は無限個存在する。 (単語は有限個)
• 英語として意味のあるものとそうでないものとが混ざっている。 ⇒ 英語として意味のある文をすべて集めた集合は、1つの言語L
(今の場合は英語)を定める。
⇒ 意味があるものとないものとを区別したい。
つまり、任意の文に対して、それが言語Lの文か否かを判定したい。

ここまでのまとめ
• 言語
 • 意味のある文の集合
• 文法の必要性
 • ある言語(例えば日本語)の文すべてを
  あらかじめ知っているなんてことは不可能!
• オートマトン
 • ある文が対象としている言語Lの文なのかを自動判定する装置