Concaténation de langages réguliers

Soient deux langages réguliers L₁, L₂. Nous allons démontrer que leur concaténation L = L₁ ∘ L₂ est aussi un langage régulier.

Qu’est-ce que la concaténation

En concaténant les deux mots « 010 » et « 1111 », on obtient le mot « 0101111 ». La concaténation de langages donne un nouveau langage, que l’on construit en concaténant chaque mot du premier langage avec chaque mot du second. Nous noterons la concaténation de deux mots ou de deux langages à l’aide d’un petit rond : ∘. On peut alors définir la concaténation des langages L₁ et L₂ ainsi :

$L_{1} \circ L_{2} = {a \circ b | a \in L_{1}, b \in L_{2}}$

Idée de la démonstration

Nous avons deux langages réguliers L₁, L₂ et deux automates qui acceptent ces langages :

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

Nous construisons un automate non déterministe A = (Q ; Σ ; δ ; q ; F) qui « contiendra » les deux automates A₁ et A₂. L’idée de base est que l’on commence à lire le mot avec l’automate A₁ et que, lorsque l’automate A₁ arrive dans un état final, on essaie d’accepter le reste du mot avec l’automate A₂. Si ce dernier accepte lui aussi cette partie du mot, alors l’automate A accepte le mot.

Exemple

Soit l’automate A₁ suivant, qui accepte les mots non vides composés uniquement de 0, ainsi que les mots composés d’un 1 suivi seulement de 0 (1, 10, 100, …) :

et l’automate A₂ suivant, qui accepte les mots qui se terminent par 01 :

Nous relions les automates ainsi : depuis tous les états finals de l’automate A₁, nous ajoutons des ε-transitions vers l’état initial de l’automate A₂, puis nous transformons les états finals de A₁ en états ordinaires. L’état initial du nouvel automate est l’état initial de l’automate A₁ :

Comment cet automate fonctionne-t-il ? On commence par simuler le fonctionnement de l’automate A₁. Si l’on arrive dans un ancien état final q₁ ou q₂, on sait que l’automate A₁ accepte une partie de ce mot. Pour que le mot entier appartienne au langage L₁ ∘ L₂, il faut que le reste du mot soit encore accepté par le second automate A₂ : c’est pourquoi de tous les anciens états finals partent des ε-transitions vers l’ancien état initial de l’automate A₂.

Prenons par exemple le mot 0001. Il appartient à la concaténation des deux langages, car il peut être obtenu en concaténant les mots 00 ∘ 01. Mais il peut tout aussi bien être obtenu en concaténant les mots 0 ∘ 001. Dans notre automate, nous pouvons simuler les deux possibilités. L’automate peut suivre ce chemin :

$q_{0} \to^{0} q_{1} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

Par ce chemin, l’automate « accepte » d’abord la partie 00 du mot, puis la partie 01. Ou bien il peut suivre ce chemin :

$q_{0} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

et l’automate « accepte » alors d’abord la partie 0 du mot, puis la partie 001. Dans les deux cas, nous arrivons bien sûr dans l’état final p₂.

Méthode formelle

Encore une fois : nous avons deux langages réguliers L₁, L₂ et deux automates qui acceptent ces langages :

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

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

Q = Q₁ ∪ Q₂ (nous supposons en même temps que Q₁ ∩ Q₂ = ∅)
Σ= Σ₁ ∪ Σ₂
q = q₀
F = F₂

Nous construisons la fonction de transition δ par étapes :

$δ (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 {p_{0}} & si & q \in F_{1} \land a = ε \\ δ_{2} (q, a) & si & q \in Q_{2} \end{cases}$

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: Complémentaire d’un langage régulier

Suivant: Étoile d’un langage régulier »