## Journal article

Publication language: KOLÁØ Du¹an and MEDUNA Alexander. Homogenous Grammars with a Reduced Number of Non-Context-Free Productions. Information Processing Letters. Amsterdam: Elsevier Science, 2002, vol. 2002, no. 81, pp. 253-257. ISSN 0020-0190. english Homogenous Grammars with a Reduced Number of Non-Context-Free Productions Homogenní gramatiky s omezeným poètem kontextových pravidel 253-257 Information Processing Letters Amsterdam, NL 2002 Information Processing Letters, Vol. 2002, No. 81, Amsterdam, NL 0020-0190 Elsevier Science grammars, phrase-structure, non-context-free productions, homogenous grammars A homogenous reduced version of grammars is introduced and discussed. A homogeneous production has its left-hand side formed by a non-empty string of identical nonterminals. A phrase-structure is homogenous if each of its productions is homogenous. The present paper discusses the reduction of homogenous grammars with respect to the number of non-context-free productions. More specifically it demonstrates that for every phrase-structure grammar, there exists an equvalent homogenous grammar that has only three non-context-free productions of the form 00 \to \epsilon, 11 \to \epsilon, and 22 \to \epsilon. @ARTICLE{ author = {Du{\v{s}}an Kol{\'{a}}{\v{r}} and Alexander Meduna}, title = {Homogenous Grammars with a Reduced Number of Non-Context-Free Productions}, pages = {253--257}, booktitle = {Information Processing Letters}, journal = {Information Processing Letters}, volume = {2002}, number = {81}, year = {2002}, location = {Amsterdam, NL}, publisher = {Elsevier Science}, ISSN = {0020-0190}, language = {english}, url = {http://www.fit.vutbr.cz/research/view_pub.php?id=6185} }