✖

Різниця регулярних мов

Нехай дано дві регулярні мови L1, L2. Доведемо, що їхня різниця L = L1 ∖ L2 також є регулярною мовою.

Ідея

Насправді майже нічого доводити не потрібно. Для різниці двох множин виконується така рівність:

L1∖L2=L1∩L2―,

де L2― — доповнення мови L2. З розділів про перетин регулярних мов і про доповнення регулярної мови ми знаємо, що регулярні мови замкнені відносно обох цих операцій. Це означає, що ми вміємо побудувати автомат, який допускає перетин мов, і автомат, який допускає доповнення мови. Тож ці автомати можна використати для побудови автомата, що допускатиме мову L1∩L2―, а це водночас і мова L1 ∖ L2.

Приклад

Нехай маємо автомат A1, який допускає всі слова з парною кількістю одиниць:

та автомат A2, який допускає слова з непарною кількістю нулів:

Побудуємо автомат, що допускатиме різницю цих мов. Для цього потрібен автомат A2―, що є доповненням автомата A2. Просто поміняємо місцями заключні та незаключні стани:

Тепер залишилося побудувати автомат A, що допускатиме перетин мов L(A1) і L(A2―):

Джерела

Розділи: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови