Fechamento das linguagens regulares

Uma linguagem L é regular se, e somente se, existe um autômato A que aceita essa linguagem, isto é, L(A) = L. Vamos demonstrar que as linguagens regulares são fechadas sob as operações de união, interseção, concatenação e fecho.

Fechamento de um conjunto sob uma operação

Dizemos que um conjunto M é fechado sob a operação ⊗ se vale que

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

Um exemplo é a operação de adição no conjunto dos números naturais. A soma de quaisquer dois números naturais é de novo um número natural. Já o conjunto dos números naturais não é fechado sob a subtração, porque, por exemplo, 7 − 15 = −8 e o número −8 não é natural.

Vamos demonstrar sob quais operações o conjunto das linguagens regulares é fechado. Todas as demonstrações serão construtivas, isto é, construiremos um autômato que aceita a linguagem resultante.