Étoile d’un langage régulier

Soit un langage régulier L. Nous allons démontrer que l’étoile du langage L est encore un langage régulier.

Qu’est-ce que l’étoile d’un langage

L’étoile (ou étoile de Kleene) d’un langage L se note L^∗. Elle contient tous les mots que l’on peut former en concaténant un nombre fini de mots du langage L. On peut la définir ainsi :

$L^{*} = {a_{1} \circ a_{2} \circ \dots \circ a_{n} | a_{i} \in L, n \in N},$

où ∘ désigne l’opération de concaténation. L’étoile contient aussi le mot vide, c’est-à-dire ϵ.

Méthode formelle

Nous procédons de façon très semblable à la concaténation de langages. Seulement, au lieu de relier deux automates différents, nous relions un automate à lui-même : depuis les états finals de l’automate, nous menons des ε-transitions vers son état initial. Cependant, l’étoile doit contenir aussi le mot vide. Comment faire ? On pourrait transformer l’état initial en état final. Un tel automate accepterait alors le mot vide, mais il pourrait aussi accepter d’autres mots qu’il ne devrait pas. C’est pourquoi nous créons plutôt un nouvel état initial, et depuis ce nouvel état initial nous menons une ε-transition vers l’ancien état initial.

Soit un langage régulier L₁ et un automate qui accepte ce langage :

$\begin{array}{rcl} A_{1} & = & (Q_{1}; Σ_{1}; δ_{1}; q_{0}; F_{1}) \end{array}$

Nous construisons un automate non déterministe A = (Q ; Σ ; δ ; q_s ; F) tel que :

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

Nous définissons la fonction de transition δ ainsi :

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & si & q \in Q_{1} \land q \notin F_{1} \\ δ_{1} (q, a) & si & q \in F_{1} \land a \neq ϵ \\ δ_{1} (q, a) \cup {q_{0}} & si & q \in F_{1} \land a = ϵ \\ {q_{0}} & si & q = q_{s} \land a = ϵ \\ \emptyset & si & q = q_{s} \land a \neq ϵ \end{cases}$

Exemple

Soit l’automate A₁ suivant, qui accepte les mots 00 ou 11 :

L’étoile du langage L(A₁) est donc le langage de tous les mots composés de blocs 00 et 11, par exemple 0000, 110011, 11110000, etc. Pour construire un automate qui accepterait cette étoile, on créerait un nouvel état initial q_s avec une ε-transition vers l’ancien état initial q₀, et l’on ajouterait des ε-transitions des états q₃ et q₄ vers l’état q₀ :

On peut vérifier que cet automate accepte bien les mots 0000, 110011, 11110000, mais qu’il n’accepte pas, par exemple, le mot 1010.

Sources

Chapitres: Propriétés de clôture des langages réguliers, Réunion de langages réguliers, Intersection de langages réguliers, Différence de langages réguliers, Complémentaire d’un langage régulier, Concaténation de langages réguliers, Étoile d’un langage régulier

« Précédent: Concaténation de langages réguliers

Suivant: Expressions régulières »