Затвореност на регулярните езици

Езикът L е регулярен тогава и само тогава, когато съществува автомат A, който приема този език, т.е. L(A) = L. Ще докажем, че регулярните езици са затворени относно операциите обединение, сечение, конкатенация и затваряне.

Затвореност на множество относно операция

Казваме, че множеството M е затворено относно операцията ⊗, ако

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

Пример за това е операцията събиране върху множеството на естествените числа. Сборът на произволни две естествени числа е отново естествено число. Обратно, множеството на естествените числа не е затворено относно изваждането, защото например 7 − 15 = −8 и числото −8 не е естествено.

Ще докажем спрямо кои операции е затворено множеството на регулярните езици. Всички доказателства ще бъдат конструктивни, т.е. ще построим автомат, който приема получения език.