A reguláris nyelvek zártsága

Az L nyelv akkor és csak akkor reguláris, ha létezik olyan A automata, amely ezt a nyelvet elfogadja, azaz L(A) = L. Bebizonyítjuk, hogy a reguláris nyelvek zártak az egyesítés, a metszet, az összefűzés és a lezárás műveletére.

Halmaz zártsága egy műveletre

Azt mondjuk, hogy az M halmaz zárt az ⊗ műveletre, ha igaz, hogy

$$\mathrm{\forall }x,y\in M:x\otimes y\in M$$

Példa erre az összeadás művelete a természetes számok halmazán. Bármely két természetes szám összege ismét természetes szám. Ezzel szemben a természetes számok halmaza nem zárt a kivonásra, mert például 7 − 15 = −8, és a −8 szám nem természetes.

Bebizonyítjuk, hogy a reguláris nyelvek halmaza mely műveletekre zárt. Minden bizonyítás konstruktív lesz, azaz megszerkesztjük azt az automatát, amely az eredményül kapott nyelvet elfogadja.