Propiedades de cierre de los lenguajes regulares

Un lenguaje L es regular si y solo si existe un autómata A que acepta ese lenguaje, es decir, L(A) = L. Demostraremos que los lenguajes regulares son cerrados respecto de las operaciones de unión, intersección, concatenación y clausura.

Cierre de un conjunto respecto de una operación

Decimos que un conjunto M es cerrado respecto de la operación ⊗ si se cumple que

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

Un ejemplo es la operación de suma en el conjunto de los números naturales. La suma de dos números naturales cualesquiera es de nuevo un número natural. En cambio, el conjunto de los números naturales no es cerrado respecto de la resta, porque, por ejemplo, 7 − 15 = −8 y el número −8 no es natural.

Demostraremos respecto de qué operaciones es cerrado el conjunto de los lenguajes regulares. Todas las demostraciones serán constructivas, es decir, construiremos un autómata que acepte el lenguaje resultante.