Uzavřenost regulárních jazyků

Jazyk L je regulární, právě tehdy, pokud existuje automat A, který tento jazyk přijímá, tj. L(A) = L. Dokážeme si, že regulární jazyky jsou uzavřené na operacích sjednocení, průnik, konkatenace a uzávěr.

Uzavřenost na množině vzhledem k operaci

Řekneme, že množina M je uzavřena na operaci $\otimes$ pokud platí, že

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

Příkladem je například operace sčítání na množině přirozených čísel. Součet jakýchkoliv dvou přirozených čísel je opět přirozené číslo. Naopak množina přirozených čísel není uzvařená na odečítání, protože například 7 − 15 = −8 a číslo −8 není přirozené.

Dokážeme si, vůči kterým operacím je uzavřena množina regulární jazyků. Všechny důkazy budou konstrukční, tj. sestrojíme automat, který přijímá výsledný jazyk.