自然言語処理や形式言語やオートマトンの学習をしていると、必ずと言っていいほど文脈自由文法（Context-Free Grammers, 以下CFGと呼ぶ）というものがでてきます。
CFGは言葉の通り文脈に依存しない文法のことで、この文法から生成される言語を文脈自由言語と呼んだりします。
CFGは正規文法を含有しているので、より豊富な表現をすることができます。
実際にC言語などのプログラミング言語の文法はCFGが多く採用されています。自然言語である英語の文法も、CFGを使ってけっこう良い感じに表現することができます。
ということで今回はCFGがどれだけ凄いかを英語の文法で確かめていきます。
文脈自由文法の形式的な定義
CFGは以下のように形式的に定義することができます。
$$
L_{0} = (N,\Sigma,R,S)
$$
\(N\): 非終端記号（あるいは変数、文法概念）の集合
\(\Sigma\): 終端記号（目的とする語を構成するアルファベット）の集合
\(R\): 生成規則（どのようにしてアルファベットを生成するか）の集合
\(S\): 開始記号（始まりを意味する非終端記号の一つ）
これだけだとおそらく抽象的にしか理解できないと思うので、実際に見ていきましょう。
<具体的な例>
\(N = {S, A}\), \(\Sigma = {0, 1}\)とし、\(R = {S \rightarrow A, A \rightarrow 0|1|0A|1A} \)で表される文脈自由文法を考えます。
この文法からどんな言語が生成されるのかを見ていくと、
S => A => 0A => 01A => 011A => 0111A => 01110A => 011100
という感じに生成されていきます。
他にわからないことがあったらココらへんを見てください。日本語なので理解しやすいと思います。
英語の文法をCFGで表現してみる
さっそく英文法をCFGで表現してみましょう。といっても全部書くと大変なことになるのでざっくり説明するだけに留めておきます。
まずは単語の品詞についてからまとめていきましょう。
flightsやbreeze, trip, morning などは同じ名詞として考えることができるので、\(Noun\)を非終端記号の一つとして名詞を表すものだとすると、以下のように表すことができます。
$$
Noun \rightarrow flights | breeze | trip | morning | …
$$
同じように is, prefer, like, need, want, … を動詞としてまとめると、
$$
Verb \rightarrow is | prefer | like | need | want | …
$$
これを続けていくと以下のように単語をまとめていくことができます。
Noun → flights | breeze | trip | morning
Verb → is | prefer | like | need | want | fly
Adjective → cheapest | non-stop | first | latest | other | direct
Pronoun → me | I | you | it
ProperNoun → Alaska | Baltimore | Los Angeles | Chicago | United | American
Determiner → the | a | an | this | these | that
Preposition → from | to | on | near
Conjunction → and | or | but
次は動詞句や名詞句といった句をモデル化していきます。
句というのは「want flight」や「morning flight」といったように複数の単語が集まって一つの意味を表しているものです。
名詞句は定冠詞や固有名詞などを考慮して以下のように定義することができます。
$$
NP \rightarrow Pronoun | ProperNoun | Det Nominal \\
Nominal \rightarrow Nominal\ Noun | Noun
$$
それぞれの非終端記号の説明をしておくと、 Pronounは代名詞で”I”や”You”などを表します。
ProperNounは”Los Angeles”などの固有名詞、Detは”a”や”this”などの限定詞、Nominalは”morning”などの名詞語句を表します。Nominal+Nounで”morning flights”などを表すことができます。
続けて動詞句についても、
$$
VP \rightarrow Verb \\
| Verb\ NP \\
| Verb\ NP\ PP \\
| Verb\ PP \\
$$
と表すことができます。
Verb+NPで”want a morning flight”みたいな動詞句を表現することができます。生成規則と非終端記号を追加していくことでどんどん表現の幅が増えていきますね。
PPは前置詞句を表す非終端記号です。以下のように定義することができます。
$$
PP \rightarrow Preposition\ NP
$$
この生成規則によって、”from + Los Angeles”といった前置詞句を表現することができます。
ここでは紹介しませんが、このように生成規則を追加していくことでさらに深いところまで英文法を表現することができます。
まとめ
今回はCFGとCFGを使って英文法をざっくり表現しました。
このようにCFGは正規文法より表現の幅が広く、プログラミング言語だけではなく英語のような自然言語の文法もある程度表現することができます。
参考文献
・5. 文脈自由文法と言語(1):
https://www.jaist.ac.jp/~uehara/course/2009/ti118/11cfg-n.pdf
・Constituency Grammars
https://web.stanford.edu/~jurafsky/slp3/12.pdf
・Context-Free Grammars for English
http://www.cs.uccs.edu/~jkalita/work/cs589/2010/12Grammars.pdf
