NLP for Dummies 2 [雑]

　

句構造文法の階層

文法G
非終端記号の集合VN、終端記号の集合VT、書換え規則の集合P、最初に書換え規則が適応される非終端記号σの4項組

VN, VT, P, σ> で定義される。

句構造文法における文の生成は、まず開始記号σを左辺に持つ書換え規則を使って、その記号σを書換え規則の右辺に書換え、新しくできた非終端記号を左辺に持つ書換え規則で、その非終端記号を書換え規則の右辺に書換え……ということを非終端記号が無くなるまで繰り返し行われる。

文法Gによって生成される文の集合L(G)を、文法Gによって生成される言語と呼ぶ。

書換え規則につけられる制限によって、句構造文法は次の4つの型に分けられる。

0型文法　書換え規則に制限がない文法
1型文法　文脈依存文法
　　　　　　 書換え規則に |α| ≦ |β| という制限をつけた文法
2型文法　文脈自由文法
　　　　　　 A → β (A ∈ VN, β ∈ (VN∪VT)+)という形をした書換え規則だけをもつ文法
3型文法　正規文法
　　　　　　 A → aB (A, B ∈ VN, a ∈ VT)、または A → a (A ∈ VN, a ∈ VT)という形をした書換え規則だけを持つ文法

これらの文法から生成される言語をそれぞれ、0型言語、1型言語、2型言語、3型言語と呼び、その包含関係は、3型言語 ⊂ 2型言語 ⊂ 1型言語 ⊂ 0型言語、となっている。