Математическая теория формальных языков
Пересечение и дополнение автоматных языков
Теорема 3.2.1.
Класс автоматных языков замкнут относительно дополнения и пересечения.
Доказательство. Если язык L распознается полным детерминированным конечным автоматом , то язык
распознается конечным автоматом .
Пересечение выражается через объединение и дополнение (закон де Моргана).
Замечание 3.2.2.
Автоматность пересечения двух автоматных языков можно легко доказать и без привлечения теоремы 2.7.1. Для этого достаточно построить по двум конечным автоматам с однобуквенными переходами
новый конечный автомат
где
Упражнение 3.2.3. Обозначим через L язык, порождаемый грамматикой
Найти праволинейную грамматику, порождающую язык .
Упражнение 3.2.4. Обозначим через L язык, порождаемый грамматикой
Найти праволинейную грамматику, порождающую язык .
Упражнение 3.2.5.
Обозначим через L язык, порождаемый грамматикой
Найти праволинейную грамматику, порождающую язык .
Упражнение 3.2.6.
Существуют ли такие детерминированные конечные автоматы M1 и M2, что язык
не порождается ни одним детерминированным конечным автоматом с количеством состояний n1n2+n1+n2, где n1 - количество состояний автомата M1
и n2 - количество состояний автомата M2?
