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 operace sjednocení, průniku, konkatenace a uzávěru.

Uzavřenost na množině vzhledem k operaci

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

$$\mathrm{\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í uzavř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ích jazyků. Všechny důkazy budou konstrukční, tj. sestrojíme automat, který přijímá výsledný jazyk.