Homogeneous grammars with a reduced number of non-context-free productions
A homogeneous production has its left-hand side formed by a non-empty string of identical nonterminals. A phrase-structure grammar is homogeneous if each of its productions is homogeneous. The present paper discusses the reduction of homogeneous grammars with respect to the number of non-context-free productions. More specifically, it demonstrates that for every phrase-structure grammar, there exists an equivalent homogeneous grammar that has only three non-context-free productions of the form 00 --> epsilon, 11 --> epsilon, and 22 --> epsilon. (C) 2002 Elsevier Science B.V. All rights reserved.
homogeneous grammars non-context-free productions reduction