Zamykanie języków regularnych

Język L jest regularny dokładnie wtedy, gdy istnieje automat A akceptujący ten język, tj. L(A) = L. Udowodnimy, że języki regularne są domknięte w operacjach unii, przecięcia, konkatenacji i domknięcia.

Domknięcie na zbiorze w odniesieniu do operacji

Mówimy, że zbiór M jest domknięty względem operacji $\otimes$, jeśli zachodzi następująca zależność

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

Przykładem jest operacja dodawania na zbiorze liczb naturalnych. Suma dowolnych dwóch liczb naturalnych jest ponownie liczbą naturalną. I odwrotnie, zbiór liczb naturalnych nie jest domknięty dla odejmowania, ponieważ na przykład 7 − 15 = −8 i liczba −8 nie są liczbami naturalnymi.

Możemy udowodnić, względem jakich operacji zbiór języków regularnych jest domknięty. Wszystkie dowody będą konstruktywne, tzn. skonstruujemy automat akceptujący wynikowy język.