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

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

Ідея

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

$$ L_1 \setminus L_2 = L_1 \cap \overline{L_2}, $$

де $\overline{L_2}$ — доповнення мови L₂. З розділів про перетин регулярних мов і про доповнення регулярної мови ми знаємо, що регулярні мови замкнені відносно обох цих операцій. Це означає, що ми вміємо побудувати автомат, який допускає перетин мов, і автомат, який допускає доповнення мови. Тож ці автомати можна використати для побудови автомата, що допускатиме мову $L_1 \cap \overline{L_2}$, а це водночас і мова L₁ ∖ L₂.

Приклад

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

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

Побудуємо автомат, що допускатиме різницю цих мов. Для цього потрібен автомат $\overline{A_2}$, що є доповненням автомата A₂. Просто поміняємо місцями заключні та незаключні стани:

Тепер залишилося побудувати автомат A, що допускатиме перетин мов L(A₁) і $L(\overline{A_2})$:

Джерела

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools