Přístupnostní navigace
E-application
Search Search Close
Publication detail
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" }