Математическая теория формальных языков
Классы эквивалентности слов
Лемма 6.4.1.
Пусть
и . Тогда
Определение 6.4.2.
Пусть
и . Обозначим через
язык . Обозначим через
язык .
Пример 6.4.3.
Пусть . Множества вида
образуют разбиение множества
на классы эквивалентности. Множества вида
образуют разбиение множества
на классы эквивалентности.
Пример 6.4.4.
Пусть
и . Тогда
Лемма 6.4.5.
Если язык
является автоматным, то для каждого слова
языки
и
являются автоматными.
Доказательство. Пусть язык L распознается конечным автоматом , не содержащим переходов с метками длины больше единицы. Будем использовать обозначение TrM
из доказательства теоремы 6.3.11. При любой фиксированной паре
язык
является автоматным (он распознается конечным автоматом ). Для каждого слова
язык
является автоматным, так как он представим в виде пересечения конечного семейства автоматных языков:
Каждый из языков [x]L
и
является объединением конечного семейства автоматных языков:
Замечание 6.4.6.
Из теоремы 6.1.8 вытекает, что если язык L автоматный, то существует лишь конечное число различных множеств . Аналогичное утверждение верно для множеств
(см. теорему 6.3.11).
Пример 6.4.7.
Рассмотрим язык
над алфавитом . Тогда
Упражнение 6.4.8.
Существуют ли такие языки
и , что язык L1
является автоматным, но язык
не является автоматным?
Упражнение 6.4.9.
Существуют ли такие языки
и , что язык L1
является автоматным, но язык
не является автоматным?
Упражнение 6.4.10.
Существует ли такой автоматный язык , что язык
не является автоматным?
Теорема 6.4.11.
Язык
является автоматным тогда и только тогда, когда существует такое отношение эквивалентности , что R разбивает
на конечное множество классов эквивалентности, L является объединением некоторых из этих классов эквивалентности и для любых , ,
из xRy следует xzRyz.
Замечание 6.4.12.
Теоремы 6.1.8 и 6.4.11 образуют теорему Майхилла-Нерода.
