Complemento de un lenguaje regular

Tomemos un lenguaje regular L. Demostraremos que el complemento del lenguaje L es de nuevo un lenguaje regular.

Qué es el complemento

Por complemento del lenguaje L entendemos todas las palabras que no están en el lenguaje L. El complemento se denota $\bar{L}$. Es decir, para el alfabeto Σ se cumple que:

$$\bar{L}=\{w\in {\mathrm{\Sigma }}^{\ast }\mid w\notin L\}.$$

Por ejemplo, para el lenguaje de las palabras que contienen al menos un símbolo 1, el complemento sería el lenguaje formado por las palabras que no contienen ningún símbolo 1.

Procedimiento

El procedimiento es muy sencillo. Tenemos un lenguaje regular L y un autómata determinista completo A = ⟨Q, Σ, δ, q₀, F⟩ que lo acepta (todo autómata finito puede convertirse en uno así). El autómata A' que acepta $\bar{L}$ lo construimos intercambiando los estados finales y los no finales: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Eso es todo.

Ejemplo

Tomemos este autómata:

El autómata que aceptara el complemento del lenguaje tendría este aspecto:

Fuentes

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