Închiderea limbajelor regulate la operații

Un limbaj L este regulat dacă și numai dacă există un automat A care acceptă acest limbaj, adică L(A) = L. Vom demonstra că limbajele regulate sunt închise la operațiile de reuniune, intersecție, concatenare și închidere Kleene.

Închiderea unei mulțimi la o operație

Spunem că o mulțime M este închisă la operația ⊗ dacă

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

Un exemplu este operația de adunare pe mulțimea numerelor naturale. Suma a două numere naturale oarecare este din nou un număr natural. În schimb, mulțimea numerelor naturale nu este închisă la scădere, deoarece, de exemplu, 7 − 15 = −8, iar numărul −8 nu este natural.

Vom demonstra față de ce operații este închisă mulțimea limbajelor regulate. Toate demonstrațiile vor fi constructive, adică vom construi un automat care acceptă limbajul rezultat.