Математическая теория формальных языков

       

Пересечение и дополнение автоматных языков


Теорема 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?



Содержание раздела