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

Type

journal article - other

Language

English

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.

Keywords

Grammar systems, derivation restriction, generative power.

Authors

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

RIV year

2011

Released

14. 3. 2011

ISBN

0860-0295

Periodical

Schedae Informaticae

Year of study

2010

Number

19

State

Republic of Poland

Pages from

23

Pages to

34

Pages count

11

BibTex

@article{BUT76285,
  author="Alexandr {Meduna} and Martin {Čermák} and Tomáš {Masopust}",
  title="Some Power-Decreasing Derivation Restrictions in Grammar Systems",
  journal="Schedae Informaticae",
  year="2011",
  volume="2010",
  number="19",
  pages="23--34",
  issn="0860-0295"
}