Up 1.5 文生成システムの類型  

　プロダクションの形式によって文生成システムの類型を定義することが考えられる。文生成システムは句構造文法(ＰＳＧ)と同じであるが，この句構造文法に関しては，以下のような類型化が伝統的になされている(註1)：

型プロダクションの形
０ φαψ→φβψ　　α∈NＶ,β∈Ｖ*
　　　　　　　　　φ,ψ∈NＶ*
１ φαψ→φβψ　　α∈NＶ,β∈Ｖ+
　　　　　　　　　φ,ψ∈NＶ*
２ α→β　　　　　　α∈NＶ,β∈Ｖ+
３ α→βかα→βγ　α,γ∈NＶ,β∈TＶ


　０,１,２,３型文法は，それぞれ句構造文法，文脈規定文法(context sensitive grammar)，文脈自由文法(context free grammar)，正規文法(regular grammar)(註2)とも呼ばれる。

　０型文法，１型文法，２型文法，３型文法は，
(1) ｎ型文法はｎ−１型文法
(2) ｎ−１型文法でｎ型文法でないものが存在する
（ｎ＝1,2,3）　　
の関係にある。


（註１） 文法のこの類型化は，オートマトンの類型化と対応している。
　例えば，有限状態オートマトン(ＦＡ)の働きが３型文法で記述でき，またプッシュダウン-オートマトン(ＰＤＡ)の働きが２型文法で記述できる。ここで,“働きが文法で記述できる”とは，働きが〈文法処理〉として記述できるということである。

（註２） 正規表現であることと３型文法によって生成されることとが同値であることによる。