✖

Доповнення регулярної мови

Нехай дано регулярну мову L. Доведемо, що доповнення мови L знову є регулярною мовою.

Що таке доповнення

Доповненням мови L називаємо всі слова, які не належать мові L. Доповнення позначаємо L―. Тобто для алфавіту Σ виконується:

L―={w∈Σ∗|w∉L}.

Наприклад, для мови слів, що містять принаймні один символ 1, доповненням була б мова, яка містить слова, що не містять жодного символу 1.

Побудова

Побудова дуже проста. Маємо регулярну мову L і детермінований повний автомат A = ⟨Q, Σ, δ, q0, F⟩, який її допускає (кожен скінченний автомат можна звести до такого). Автомат A―, що допускає L―, побудуємо, помінявши місцями заключні та незаключні стани: A―=⟨Q,Σ,δ,q0,Q∖F⟩. Це все.

Приклад

Нехай маємо такий автомат:

Автомат, що допускає доповнення мови, виглядав би так:

Джерела

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