Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2011

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: inverse context free systems

Sortuj według:

Ogranicz wyniki do:

On McNaughton Families of Languages That Are Specified by Some Variants of Monadic String-Rewriting Systems

Leupold P., Otto F.

Fundamenta Informaticae

2011

Vol. 112, nr 2/3

219-238

We study the McNaughton families of languages that are specified by four different variants of monadic string-rewriting systems: strictly monadic systems, monadic systems, inverse context-free systems, and generalized monadic systems. In the general case these four variants yield the same McNaughton family of languages, which coincides with the class of context-free languages. In the case of confluent systems, however, we obtain two McNaughton families by showing that special rules, that is, rules with empty right-hand side, are not needed. This implies that in this situation strictly monadic systems are as expressive as monadic systems, and inverse context-free systems are as expressive as generalized monadic systems. The McNaughton family defined by the former systems is contained in the McNaughton family that is defined by the latter systems, and this inclusion is proper if and only if the former family is not closed under inverse alphabeticmorphisms. Finally, we show that the latter family is a proper subclass of the class of deterministic context-free languages.