Publication Details

Homogenous Grammars with a Reduced Number of Non-Context-Free Productions

KOLÁŘ Dušan and MEDUNA Alexander. Homogenous Grammars with a Reduced Number of Non-Context-Free Productions. Information Processing Letters, vol. 2002, no. 81, pp. 253-257. ISSN 0020-0190.
Czech title
Homogenní gramatiky s omezeným počtem kontextových pravidel
Type
journal article
Language
english
Authors
Kolář Dušan, doc. Dr. Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Keywords

grammars, phrase-structure, non-context-free productions, homogenous grammars

Abstract

A homogenous reduced version of grammars is introduced and discussed.

Annotation

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.

Published
2002
Pages
253-257
Journal
Information Processing Letters, vol. 2002, no. 81, ISSN 0020-0190
Book
Information Processing Letters
Publisher
Elsevier Science
Place
Amsterdam, NL
BibTeX 
@ARTICLE{FITPUB6185,
   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 = "https://www.fit.vut.cz/research/publication/6185"
}
Back to top