Afgeslotenheid van reguliere talen

Een taal L is regulier dan en slechts dan als er een automaat A bestaat die deze taal accepteert, dus L(A) = L. We bewijzen dat reguliere talen afgesloten zijn onder de bewerkingen vereniging, doorsnede, concatenatie en afsluiting.

Afgeslotenheid van een verzameling onder een bewerking

We zeggen dat een verzameling M afgesloten is onder een bewerking ⊗ als

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

Een voorbeeld is de bewerking optellen op de verzameling van de natuurlijke getallen. De som van twee willekeurige natuurlijke getallen is weer een natuurlijk getal. De verzameling van de natuurlijke getallen is daarentegen niet afgesloten onder aftrekken, want bijvoorbeeld 7 − 15 = −8 en het getal −8 is niet natuurlijk.

We bewijzen onder welke bewerkingen de verzameling van de reguliere talen afgesloten is. Alle bewijzen zijn constructief, dat wil zeggen dat we een automaat construeren die de resulterende taal accepteert.