PL EN


Preferences help
enabled [disable] Abstract
Number of results
2010 | 19 |
Article title

Some Power-Decreasing Derivation Restrictions in Grammar Systems

Content
Title variants
Languages of publication
PL
Abstracts
PL
In this paper, we place some left restrictions on derivations in CD grammar systems with phrase- structure grammars, controlled by the regular languages. The rst restriction requires that every production is always applied within the rst k nonterminals in every sentential form, for some k 1. The second restriction says how many blocks of non-terminals can be in each sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in each sentential form. We demonstrate that under these restrictions, the grammar systems generate dierent families of languages. Indeed, under the rst restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enumerable languages. In the end, the family of languages generated by grammar systems under the third restriction is equal to the family of languages generated by programmed grammars with context-free rules without -rules of nite index.
Publisher
Year
Volume
19
Physical description
Dates
published
2010
online
08 - 07 - 2015
Contributors
References
Document Type
Publication order reference
Identifiers
YADDA identifier
bwmeta1.element.ojs-issn-2083-8476-year-2010-volume-19-article-2998
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.