Clausura de un lenguaje regular

Tenemos un lenguaje regular L. Demostraremos que la clausura de Kleene del lenguaje L es de nuevo un lenguaje regular.

Qué es la clausura de un lenguaje

La clausura (de Kleene) del lenguaje L se denota L^∗. Contiene todas las palabras que se pueden formar concatenando una cantidad finita de palabras del lenguaje L. La clausura puede definirse como:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n\mid a_i\in L,n\in {\mathbb{N}}_0\},$$

donde ∘ denota la operación de concatenación. La clausura contiene también la palabra vacía, es decir, ϵ.

Procedimiento formal

Procederemos de forma muy parecida al caso de la concatenación de lenguajes. Solo que, en lugar de conectar dos autómatas distintos, conectaremos un autómata consigo mismo: desde los estados finales del autómata trazaremos transiciones ε hacia su estado inicial. Sin embargo, la clausura debe contener también la palabra vacía. ¿Cómo conseguirlo? Podríamos convertir el estado inicial en final. Entonces ese autómata aceptaría la palabra vacía, pero podría aceptar también alguna otra palabra que no debe. Por eso, en su lugar creamos un nuevo estado inicial y desde él trazamos una transición ε hacia el estado inicial original.

Tenemos un lenguaje regular L₁ y un autómata que acepta este lenguaje:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

Construimos un autómata no determinista A = ⟨Q, Σ, δ, q_s, F⟩ que cumple:

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

La función de transición δ la definimos así:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{si}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{si}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{si}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{si}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{si}& q=q_s\wedge a\ne ϵ\end{array}$$

Ejemplo

Tomemos este autómata A₁, que acepta las palabras 00 o 11:

La clausura del lenguaje L(A₁) es, pues, el lenguaje de todas las palabras formadas por parejas 00 y 11, por ejemplo 0000, 110011, 11110000, etc. El autómata que aceptara esta clausura lo construiríamos creando un nuevo estado inicial q_s con una transición ε hacia el antiguo estado inicial q₀ y añadiendo transiciones ε desde los estados q₃ y q₄ hacia el estado q₀:

Podemos comprobar que este autómata acepta realmente las palabras 0000, 110011, 11110000, pero no acepta, por ejemplo, la palabra 1010.

Fuentes

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