Your Cart

Your cart is empty

Home  >  Volume 36 (no2)

Reduction of Generalized Forbidding Grammars by R.O. Oladele and A.A. Ajayi (page 11-14)
Sale price: $5.00


In this paper, we improve the upper bounds of certain descriptional complexity measures of generalized forbidding grammars. We prove that a generalized forbidding grammar of degree 2 with no morethan 6 conditional productions and 8 non-terminals is sufficient to generate the class of recursively enumerable language. This result is based on the common idea of using the so-called Geffert normal forms for phrase structure grammars.

Key words: descriptional complexity, generalized forbidding grammars, formal languages