Fecho de uma linguagem regular

Temos uma linguagem regular L. Vamos demonstrar que o fecho da linguagem L é de novo uma linguagem regular.

O que é o fecho de uma linguagem

O fecho da linguagem L é denotado por L^∗. O fecho contém todas as palavras que podem ser formadas pela concatenação de uma quantidade finita de palavras da linguagem L. Podemos definir o fecho como:

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

em que ∘ representa a operação de concatenação. O fecho contém também a palavra vazia, isto é, ϵ.

Procedimento formal

Vamos proceder de forma muito parecida com o caso da concatenação de linguagens. Só que, em vez de ligar dois autômatos diferentes, ligamos um único autômato — dos estados finais do autômato levamos transições ε até o estado inicial do autômato. No entanto, o fecho deve conter também a palavra vazia. Como providenciar isso? Podemos transformar o estado inicial em um estado final. Aí o autômato aceitaria a palavra vazia, mas poderia aceitar também alguma outra palavra indesejada. Por isso, em vez disso, criamos um novo estado inicial e desse novo estado inicial levamos uma transição ε até o estado inicial original.

Temos uma linguagem regular L₁ e um autômato que aceita essa linguagem:

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

Construímos o autômato não determinístico A = ⟨Q, Σ, δ, q_s, F⟩, para o qual vale:

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

Definimos a função de transição δ assim:

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

Exemplo

Considere este autômato A₁, que aceita as palavras 00 ou 11:

O fecho da linguagem L(A₁) é, assim, a linguagem de todas as palavras compostas de pares 00 e 11, por exemplo 0000, 110011, 11110000 etc. Construiríamos o autômato que aceitaria esse fecho criando um novo estado inicial q_s com uma transição ε para o ex-estado inicial q₀ e acrescentando transições ε dos estados q₃ e q₄ para o estado q₀:

Podemos verificar que esse autômato de fato aceita as palavras 0000, 110011, 11110000, mas não aceita, por exemplo, a palavra 1010.

Fontes

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