Замкненість регулярних мов

Мова L регулярна тоді й лише тоді, коли існує автомат A, що допускає цю мову, тобто L(A) = L. Доведемо, що регулярні мови замкнені відносно операцій об'єднання, перетину, конкатенації та замикання Кліні.

Замкненість множини відносно операції

Кажемо, що множина M замкнена відносно операції $\otimes$, якщо виконується

$$ \forall x, y \in M: x \otimes y \in M $$

Прикладом є операція додавання на множині натуральних чисел. Сума будь-яких двох натуральних чисел знову є натуральним числом. Натомість множина натуральних чисел не замкнена відносно віднімання, бо, наприклад, 7 − 15 = −8, а число −8 не є натуральним.

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