Доповнення регулярної мови
Kapitoly: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови
Нехай дано регулярну мову L. Доведемо, що доповнення мови L знову є регулярною мовою.
Що таке доповнення
Доповненням мови L називаємо всі слова, які не належать мові L. Доповнення позначаємо $\overline{L}$. Тобто для алфавіту $\Sigma$ виконується:
$$ \overline{L} = \left\{w \in \Sigma^\ast,|, w \notin L\right\}. $$
Наприклад, для мови слів, що містять принаймні один символ 1, доповненням була б мова, яка містить слова, що не містять жодного символу 1.
Побудова
Побудова дуже проста. Маємо регулярну мову L і детермінований повний автомат $A=\left<Q, \Sigma, \delta, q_0, F\right>$, який її допускає (кожен скінченний автомат можна звести до такого). Автомат $\overline{A}$, що допускає $\overline{L}$, побудуємо, помінявши місцями заключні та незаключні стани: $\overline{A}=\left<Q, \Sigma, \delta, q_0, Q\setminus F\right>$. Це все.
Приклад
Нехай маємо такий автомат:
Автомат, що допускає доповнення мови, виглядав би так:
