Säännöllisten kielten sulkeumaominaisuudet

Kieli L on säännöllinen täsmälleen silloin, kun on olemassa automaatti A, joka hyväksyy tämän kielen, eli L(A) = L. Todistamme, että säännölliset kielet ovat suljettuja yhdisteen, leikkauksen, konkatenaation ja Kleenen tähden suhteen.

Joukon sulkeutuminen operaation suhteen

Sanomme, että joukko M on suljettu operaation ⊗ suhteen, jos pätee

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

Esimerkkinä on vaikkapa yhteenlasku luonnollisten lukujen joukossa. Minkä tahansa kahden luonnollisen luvun summa on jälleen luonnollinen luku. Sen sijaan luonnollisten lukujen joukko ei ole suljettu vähennyslaskun suhteen, koska esimerkiksi 7 − 15 = −8 eikä luku −8 ole luonnollinen.

Todistamme, minkä operaatioiden suhteen säännöllisten kielten joukko on suljettu. Kaikki todistukset ovat konstruktiivisia, eli rakennamme automaatin, joka hyväksyy tuloksena syntyvän kielen.