Chiusura di Kleene di un linguaggio regolare

Sia L un linguaggio regolare. Dimostreremo che la chiusura di Kleene del linguaggio L è ancora un linguaggio regolare.

Cos’è la chiusura di Kleene di un linguaggio

La chiusura di Kleene del linguaggio L si indica con L^∗. Contiene tutte le parole che si possono ottenere concatenando un numero finito di parole del linguaggio L. Possiamo definirla così:

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

dove ∘ indica l’operazione di concatenazione. La chiusura contiene anche la parola vuota, cioè ϵ.

Procedimento formale

Procederemo in modo molto simile al caso della concatenazione di linguaggi. Solo che, invece di collegare due automi diversi, colleghiamo un automa con se stesso: dagli stati finali dell’automa facciamo partire ε-transizioni verso lo stato iniziale dell’automa. Però la chiusura deve contenere anche la parola vuota. Come fare? Potremmo rendere finale lo stato iniziale. In tal modo l’automa accetterebbe la parola vuota, ma potrebbe accettare anche qualche altra parola che non deve. Per questo creiamo invece un nuovo stato iniziale e da questo nuovo stato iniziale facciamo partire una ε-transizione verso lo stato iniziale originario.

Abbiamo un linguaggio regolare L₁ e un automa che lo accetta:

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

Costruiamo un automa non deterministico A = ⟨Q, Σ, δ, q_s, F⟩ per cui vale:

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

La funzione di transizione δ si definisce così:

$$\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}$$

Esempio

Consideriamo questo automa A₁, che accetta le parole 00 oppure 11:

La chiusura di Kleene del linguaggio L(A₁) è quindi il linguaggio di tutte le parole formate da coppie 00 e 11, ad esempio 0000, 110011, 11110000 ecc. L’automa che accetta questa chiusura si costruisce creando un nuovo stato iniziale q_s con una ε-transizione verso l’ex stato iniziale q₀ e aggiungendo ε-transizioni dagli stati q₃ e q₄ verso lo stato q₀:

Possiamo verificare che questo automa accetta davvero le parole 0000, 110011, 11110000, ma non accetta ad esempio la parola 1010.

Fonti

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