Slutenhet hos reguljära språk

Ett språk L är reguljärt om och endast om det finns en automat A som accepterar språket, dvs. L(A) = L. Vi bevisar att reguljära språk är slutna under operationerna union, snitt, konkatenering och Kleenestjärna.

Slutenhet hos en mängd under en operation

Vi säger att en mängd M är sluten under operationen ⊗ om det gäller att

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

Ett exempel är addition på mängden av naturliga tal. Summan av två naturliga tal är alltid ett naturligt tal. Däremot är mängden av naturliga tal inte sluten under subtraktion, eftersom till exempel 7 − 15 = −8 och talet −8 inte är naturligt.

Vi ska bevisa under vilka operationer mängden av reguljära språk är sluten. Alla bevis blir konstruktiva, dvs. vi konstruerar en automat som accepterar det resulterande språket.