Lukkethet av regulære språk

Et språk L er regulært hvis og bare hvis det finnes en automat A som aksepterer dette språket, altså L(A) = L. Vi skal bevise at regulære språk er lukket under operasjonene union, snitt, konkatenering og Kleene-stjerne.

Lukkethet av en mengde under en operasjon

Vi sier at en mengde M er lukket under operasjonen ⊗ hvis

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

Et eksempel er addisjon på mengden av naturlige tall. Summen av to vilkårlige naturlige tall er igjen et naturlig tall. Mengden av naturlige tall er derimot ikke lukket under subtraksjon, for eksempel er 7 − 15 = −8, og tallet −8 er ikke naturlig.

Vi skal bevise hvilke operasjoner mengden av regulære språk er lukket under. Alle bevisene blir konstruktive, det vil si at vi konstruerer en automat som aksepterer det resulterende språket.