Різниця регулярних мов
Нехай дано дві регулярні мови L1, L2. Доведемо, що їхня різниця L = L1 ∖ L2 також є регулярною мовою.
Ідея
Насправді майже нічого доводити не потрібно. Для різниці двох множин виконується така рівність:
де
Приклад
Нехай маємо автомат A1, який допускає всі слова з парною кількістю одиниць:
та автомат A2, який допускає слова з непарною кількістю нулів:
Побудуємо автомат, що допускатиме різницю цих мов. Для цього потрібен автомат
Тепер залишилося побудувати автомат A, що допускатиме перетин мов L(A1) і
Джерела
Розділи: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови