Publication Details

One-Sided Forbidding Grammars and Selective Substitution Grammars

MEDUNA, A.; ZEMEK, P. One-Sided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics, 2012, vol. 89, no. 5, p. 586-596. ISSN: 0020-7160.
Czech title
Jednostranné zakazující gramatiky a selektivní gramatiky
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Zemek Petr, Ing., Ph.D.
URL
Keywords

Formal language theory, regulated rewriting, one-sided forbidding grammars,
selective substitution grammars, generative power

Abstract

In one-sided forbidding grammars, the set of rules is divided into the set of
left forbidding rules and the set of right forbidding rules. A left forbidding
rule can rewrite a nonterminal if each of its forbidding symbols is absent to the
left of the rewritten symbol in the current sentential form while a right
forbidding rule is applied analogically except that this absence is verified to
the right. Apart from this, they work like ordinary forbidding grammars.

As its main result, the present paper proves that one-sided forbidding grammars
are equivalent to selective substitution grammars. This equivalence is
established in terms of grammars with and without erasing rules. Furthermore, the
paper proves that one-sided forbidding grammars in which the set of left
forbidding rules coincides with the set of right forbidding rules characterize
the family of context-free languages. In the conclusion, the significance of the
achieved results is discussed.

Published
2012
Pages
586–596
Journal
International Journal of Computer Mathematics, vol. 89, no. 5, ISSN 0020-7160
DOI
UT WoS
000300852300001
BibTeX
@article{BUT91446,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Forbidding Grammars and Selective Substitution Grammars",
  journal="International Journal of Computer Mathematics",
  year="2012",
  volume="89",
  number="5",
  pages="586--596",
  doi="10.1080/00207160.2011.642300",
  issn="0020-7160",
  url="http://www.tandfonline.com/doi/abs/10.1080/00207160.2011.642300"
}
Back to top