Publication result detail

One-Sided Forbidding Grammars and Selective Substitution Grammars

MEDUNA, A.; ZEMEK, P.

Original Title

One-Sided Forbidding Grammars and Selective Substitution Grammars

English Title

One-Sided Forbidding Grammars and Selective Substitution Grammars

Type

WoS Article

Original 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.

English 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.

Keywords

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

Key words in English

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

Authors

MEDUNA, A.; ZEMEK, P.

RIV year

2013

Released

01.03.2012

ISBN

0020-7160

Periodical

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Volume

89

Number

5

State

United Kingdom of Great Britain and Northern Ireland

Pages from

586

Pages to

596

Pages count

11

URL

http://www.tandfonline.com/doi/abs/10.1080/00207160.2011.642300

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"
}