Publication detail

Generalized One-Sided Forbidding Grammars

MEDUNA, A. ZEMEK, P.

Original Title

Generalized One-Sided Forbidding Grammars

English Title

Generalized One-Sided Forbidding Grammars

Type

journal article - other

Language

en

Original Abstract

In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.

English abstract

In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.

Keywords

formal languages, regulated rewriting, generalized one-sided forbidding grammars, language families, generative power

RIV year

2013

Released

01.01.2013

Publisher

NEUVEDEN

Location

NEUVEDEN

ISBN

0020-7160

Periodical

International Journal of Computer Mathematics

Year of study

90

Number

2

State

GB

Pages from

172

Pages to

182

Pages count

11

URL

Documents

BibTex


@article{BUT103403,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Generalized One-Sided Forbidding Grammars",
  annote="In generalized one-sided forbidding grammars (GOFGs), each context-free rule has
associated a finite set of forbidding strings, and the set of rules is divided
into the sets of left and right forbidding rules. A left forbidding rule can
rewrite a nonterminal if each of its forbidding strings is absent to the left of
the rewritten symbol. A right forbidding rule is applied analogically. Apart from
this, they work like any generalized forbidding grammar. This paper proves the
following three results. (1) GOFGs where each forbidding string consists of at
most two symbols characterize the family of recursively enumerable languages. (2)
GOFGs where the rules in one of the two sets of rules contain only ordinary
context-free rules without any forbidding strings characterize the family of
context-free languages. (3) GOFGs with the set of left forbidding rules
coinciding with the set of right forbidding rules characterize the family of
context-free languages.",
  address="NEUVEDEN",
  chapter="103403",
  doi="10.1080/00207160.2012.723703",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="2",
  volume="90",
  year="2013",
  month="january",
  pages="172--182",
  publisher="NEUVEDEN",
  type="journal article - other"
}