Diferencia de lenguajes regulares

Tomemos dos lenguajes regulares L₁, L₂. Demostraremos que su diferencia L = L₁ ∖ L₂ es también un lenguaje regular.

Idea

En realidad no hay mucho que demostrar. Para la diferencia de dos conjuntos se cumple la siguiente relación:

$$L_1\setminus L_2=L_1\cap \overline{L_2},$$

donde $\overline{L_2}$ es el complemento del lenguaje L₂. Por los capítulos sobre la intersección de lenguajes regulares y el complemento de un lenguaje regular sabemos que los lenguajes regulares son cerrados respecto de ambas operaciones. Esto significa que podemos construir un autómata que acepte la intersección de lenguajes y el complemento de un lenguaje. Podemos usar estos autómatas para construir un autómata que acepte el lenguaje $L_1\cap \overline{L_2}$, que es a la vez el lenguaje L₁ ∖ L₂.

Ejemplo

Tomemos este autómata A₁, que acepta todas las palabras que contienen un número par de 1:

y el autómata A₂, que acepta las palabras que contienen un número impar de 0:

Construimos un autómata que aceptará la diferencia de estos lenguajes. Necesitamos, por tanto, un autómata A₂′ que sea el complemento del autómata A₂. Basta intercambiar los estados finales y los no finales:

Ahora solo nos queda construir el autómata A que aceptará la intersección de los lenguajes L(A₁) y L(A₂′):

Fuentes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools