チョムスキーの考え出した句構造規則は、その規則の形によって、作れる文章の複雑さが変わるようです。

そして、文法を複雑さに応じて分類したものを「チョムスキー階層」と呼ばれています。

また、文法の表現方法には、「生成系」という文章を作るための書き方と、「受理系」という文章を分析するための書き方があるようです。

生成系の文法は、「終端記号Σ」「非終端記号P」「生成規則N」の各集合と、非終端記号の一種の「開始記号S」から構成されています。

生成系では文章は、「非終端記号」を「終端記号」になるまで、「生成規則」に従って置き換えてゆくことで作られます。そして、生成できる文章の複雑さは、「生成規則」の形に応じて決まるわけです。

参考文献

『形式言語の理論』

形式文法について知ろうとしたとき、詳しく書いてある本が意外と見つかりません。

『計算理論の基礎』や『ファインマン計算機科学』などは、オートマトンの受理系についてはよく書いてありますが、生成系の方は余り書いてありません。しかも、同じ文脈自由文法でも、書き方が沢山あるため、訳が分からなくなってきます。

必要なところをざっと見ただけですが、この本は、正規文法から、文脈依存文法まで整理して書かれていて、いい感じでした。