Închiderea Kleene a unui limbaj regulat

Fie un limbaj regulat L. Vom demonstra că închiderea Kleene a limbajului L este tot un limbaj regulat.

Ce este închiderea unui limbaj

Închiderea Kleene a limbajului L se notează L^∗. Ea conține toate cuvintele care se pot forma concatenând un număr finit de cuvinte din limbajul L. Închiderea o putem defini astfel:

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

unde ∘ denotă operația de concatenare. Închiderea conține și cuvântul vid, adică ϵ.

Construcția formală

Vom proceda foarte asemănător ca în cazul concatenării limbajelor. Doar că, în loc să legăm două automate diferite, legăm un singur automat – din stările finale ale automatului ducem ε-tranziții în starea inițială a automatului. Totuși, închiderea trebuie să conțină și cuvântul vid. Cum rezolvăm asta? Am putea face din starea inițială o stare finală. Atunci un astfel de automat ar accepta cuvântul vid, dar ar putea accepta și alte cuvinte în plus. De aceea, în schimb, creăm o nouă stare inițială și din această nouă stare inițială ducem o ε-tranziție în starea inițială originală.

Avem un limbaj regulat L₁ și un automat care acceptă acest limbaj:

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

Construim un automat nedeterminist A = ⟨Q, Σ, δ, q_s, F⟩ pentru care are loc:

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

Funcția de tranziție δ o definim astfel:

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

Exemplu

Fie automatul A₁, care acceptă cuvintele 00 sau 11:

Închiderea Kleene a limbajului L(A₁) este deci limbajul tuturor cuvintelor formate din perechi 00 și 11, de exemplu 0000, 110011, 11110000 etc. Automatul care ar accepta această închidere l-am construi creând o nouă stare inițială q_s cu o ε-tranziție în fosta stare inițială q₀ și adăugând ε-tranziții din stările q₃ și q₄ în starea q₀:

Putem verifica faptul că acest automat acceptă într-adevăr cuvintele 0000, 110011, 11110000, dar nu acceptă, de pildă, cuvântul 1010.

Surse

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