Full-text resources of PSJD and other databases are now available in the new Library of Science.
Visit https://bibliotekanauki.pl

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.