Publication Details

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

KOLÁŘ, D.; MEDUNA, A. Homogenous Grammars with a Reduced Number of Non-Context-Free Productions. Information Processing Letters, 2002, vol. 2002, no. 81, p. 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)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)

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

BibTeX

@article{BUT41074,
  author="Dušan {Kolář} and Alexandr {Meduna}",
  title="Homogenous Grammars with a Reduced Number of Non-Context-Free Productions",
  journal="Information Processing Letters",
  year="2002",
  volume="2002",
  number="81",
  pages="253--257",
  issn="0020-0190"
}