Domkniętość języków regularnych

Język L jest regularny wtedy i tylko wtedy, gdy istnieje automat A, który ten język akceptuje, czyli L(A) = L. Udowodnimy, że języki regularne są domknięte ze względu na operacje sumy, przecięcia, konkatenacji i domknięcia Kleene’ego.

Domkniętość zbioru ze względu na działanie

Powiemy, że zbiór M jest domknięty ze względu na działanie $\otimes$, jeśli zachodzi

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

Przykładem jest dodawanie w zbiorze liczb naturalnych. Suma dowolnych dwóch liczb naturalnych jest znowu liczbą naturalną. Natomiast zbiór liczb naturalnych nie jest domknięty ze względu na odejmowanie, bo na przykład 7 − 15 = −8, a liczba −8 nie jest naturalna.

Udowodnimy, ze względu na które operacje jest domknięty zbiór języków regularnych. Wszystkie dowody będą konstrukcyjne, czyli zbudujemy automat, który akceptuje wynikowy język.