Доповнення регулярної мови
Нехай дано регулярну мову L. Доведемо, що доповнення мови L знову є регулярною мовою.
Що таке доповнення
Доповненням мови L називаємо всі слова, які не належать мові L. Доповнення позначаємо
Наприклад, для мови слів, що містять принаймні один символ 1, доповненням була б мова, яка містить слова, що не містять жодного символу 1.
Побудова
Побудова дуже проста. Маємо регулярну мову L і детермінований повний автомат A = ⟨Q, Σ, δ, q0, F⟩, який її допускає (кожен скінченний автомат можна звести до такого). Автомат
Приклад
Нехай маємо такий автомат:
Автомат, що допускає доповнення мови, виглядав би так:
Джерела
Розділи: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови