Lukkethed af regulære sprog

Et sprog L er regulært, netop hvis der findes en automat A, som accepterer dette sprog, dvs. L(A) = L. Vi viser, at regulære sprog er lukkede under operationerne forening, fællesmængde, konkatenering og Kleene-stjerne.

Lukkethed af en mængde under en operation

Vi siger, at en mængde M er lukket under operationen ⊗, hvis

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

Et eksempel er operationen addition på mængden af naturlige tal. Summen af to vilkårlige naturlige tal er igen et naturligt tal. Omvendt er mængden af naturlige tal ikke lukket under subtraktion, fordi for eksempel 7 − 15 = −8, og tallet −8 er ikke naturligt.

Vi viser, under hvilke operationer mængden af regulære sprog er lukket. Alle beviser bliver konstruktive, dvs. vi konstruerer en automat, som accepterer det resulterende sprog.