Publication detail

Some Power-Decreasing Derivation Restrictions in Grammar Systems

MEDUNA, A. ČERMÁK, M. MASOPUST, T.

Original Title

Some Power-Decreasing Derivation Restrictions in Grammar Systems

English Title

Some Power-Decreasing Derivation Restrictions in Grammar Systems

Type

journal article - other

Language

en

Original Abstract

The paper, places some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by regular languages. The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for some k=1,...,n. The second restriction says how many blocks of non-terminals can be in every sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in every sentential form. We demonstrate that under these restrictions, the grammar systems generate different families of languages.

English abstract

The paper, places some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by regular languages. The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for some k=1,...,n. The second restriction says how many blocks of non-terminals can be in every sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in every sentential form. We demonstrate that under these restrictions, the grammar systems generate different families of languages.

Keywords

Grammar systems, derivation restriction, generative power.

RIV year

2011

Released

14.03.2011

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

23

Pages to

34

Pages count

11

Documents

BibTex


@article{BUT76285,
  author="Alexandr {Meduna} and Martin {Čermák} and Tomáš {Masopust}",
  title="Some Power-Decreasing Derivation Restrictions in Grammar Systems",
  annote="The paper, places some left restrictions on derivations in CD grammar systems
with phrase-structure grammars, controlled by regular languages. The first
restriction requires that every production is always applied within the
first k nonterminals in every sentential form, for some k=1,...,n. The second
restriction says how many blocks of non-terminals can be in every sentential
form. The third restriction extends the second restriction and says how many
blocks of non-terminals with limited length can be in every sentential form. We
demonstrate that under these restrictions, the grammar systems generate different
families of languages.",
  address="NEUVEDEN",
  booktitle="Schedae Informaticae",
  chapter="76285",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="19",
  volume="2010",
  year="2011",
  month="march",
  pages="23--34",
  publisher="NEUVEDEN",
  type="journal article - other"
}