Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Schedae Informaticae

1 2010

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: grammar systems

Sortuj według:

Ogranicz wyniki do:

Some power - decreasing derivation restrictions in grammar systems

Meduna A., Čermák M., Masopust T.

Schedae Informaticae

2010

Vol. 19

23-34

In this paper, we place some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by the regular languages. The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for some k greather than 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 different families of languages. Irideed, under the first restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enu-merable 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 e-rules of finite index.