Réunion de langages réguliers

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

Méthode avec un automate déterministe

Idée de la méthode

Nous avons deux langages réguliers L₁ et L₂ et nous voulons démontrer que leur réunion L₁ ∪ L₂ est de nouveau un langage régulier. Comme L₁ et L₂ sont réguliers, il existe des automates finis A₁ et A₂ qui acceptent les langages L₁ et L₂, c’est-à-dire que L(A₁) = L₁ et L(A₂) = L₂. Nous construisons ensuite un automate fini A qui accepte le langage L₁ ∪ L₂, ce qui prouve que le langage L₁ ∪ L₂ est régulier.

Comment faire ? Nous disposons des automates finis A₁ et A₂, qui acceptent chacun un des langages. On peut dire qu’un mot w appartient au langage L₁ ∪ L₂ si et seulement si au moins l’un des automates A₁ ou A₂ l’accepte.

L’automate A pourrait fonctionner ainsi : pour une entrée w, il simule le calcul de l’automate A₁ sur l’entrée w. Si A₁ accepte le mot w, alors A accepte aussi le mot w. Si A₁ rejette le mot w, alors A essaie de simuler le calcul de A₂ sur l’entrée w. Si A₂ accepte le mot w, alors A accepte aussi le mot w. Sinon, il le rejette.

Il nous reste à formaliser ce que signifie que l’automate A « simule » le calcul d’un autre automate.

Formalisation

Nous avons deux langages réguliers L₁ et L₂, acceptés par les automates finis

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

Nous construisons un automate fini A = (Q ; Σ ; δ ; q ; F) qui accepte le langage L = L₁ ∪ L₂. Nous utilisons l’idée de simuler deux automates A₁, A₂. Imaginons que l’entrée est le mot w = w₁w₂… w_n et que nous simulons simultanément le déroulement des automates A₁ et A₂ sur le mot w. La configuration initiale de l’automate A₁ est (q₁ ; w₁w₂… w_n), celle de A₂ est (q₂ ; w₁w₂… w_n). Effectuons maintenant une étape de calcul dans chaque automate, ce qui nous amène aux configurations (δ₁(q₁, w₁) ; w₂… w_n) et (δ₂(q₂, w₁) ; w₂… w_n).

Nous voyons que ces configurations ne diffèrent que par leur première composante ; la seconde – la partie non lue du mot – est toujours la même. Pendant la simulation, nous n’avons donc pas besoin de garder deux configurations de deux automates : une seule configuration de la forme (⟨q_i, q_j⟩ ; w_l… w_n) suffit, où q_i ∈ Q₁ et q_j ∈ Q₂. Autrement dit, notre automate A aura pour configuration initiale (⟨q₁, q₂⟩ ; w). La première composante du couple ⟨q₁, q₂⟩ représente l’état dans lequel se trouve actuellement l’automate A₁, la seconde l’état actuel de l’automate A₂.

Nous pouvons donc écrire que l’ensemble des états de l’automate A à construire est Q = Q₁ × Q₂. C’est le produit cartésien des ensembles d’états des deux automates précédents. L’idée suivante est que l’automate A a pour état initial ⟨q₁, q₂⟩ et que, si l’automate A₁ passe à l’état q_i en lisant la lettre w₁ et l’automate A₂ à l’état q_j en lisant la lettre w₁, alors l’automate A passe à l’état ⟨q_i, q_j⟩ en lisant la lettre w₁.

Nous écrivons la fonction de transition δ ainsi (on suppose ici que nous sommes actuellement dans les états q_i et q_j) :

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Il ne reste que quelques détails à régler. Pour l’alphabet, on a Σ= Σ₁ ∪ Σ₂. L’état initial est q = ⟨q₁, q₂⟩. Et les états finals sont tous les couples ⟨q_i, q_j⟩ tels que q_i ∈ F₁ ou q_j ∈ F₂.

Illustration de la méthode

Prenons deux automates. Le premier est l’automate A₁, qui accepte tous les mots (y compris le mot vide) où les 0 et les 1 alternent, c’est-à-dire les mots de la forme 01, 0101, 010101, …

L’autre automate A₂ accepte les mots qui contiennent au moins un 0 :

La réunion de ces langages est formée des mots qui contiennent un 0 ou qui sont de la forme 01, 0101, … Construisons maintenant l’automate fini A = (Q ; Σ ; δ ; q ; F) qui accepte exactement ce langage réunion. Voyons d’abord à quoi ressemblent les états de ce nouvel automate A. Ce sera le produit cartésien des ensembles d’états du premier et du second automate :

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

Voici les six états de l’automate A qui accepte le langage réunion L(A₁) ∪ L(A₂). Dans le diagramme, ils ressembleraient à ceci :

Ne t’inquiète pas de voir des états formés de couples d’états – cela sert seulement à mieux s’y retrouver dans ce qui se passe dans l’automate. Les états pourraient très bien s’appeler simplement q₀, …, q₅. Les états finals sont ceux qui contiennent l’état q₀ ou p₁, qui sont les états finals des automates d’origine. L’état initial est ⟨q₀, p₀⟩.

Il faut maintenant trouver toutes les transitions. Écrivons un tableau :

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Et remplissons-le peu à peu. On cherche d’abord où mène la transition depuis l’état ⟨q₀, p₀⟩ avec l’entrée 0. On regarde où mène la transition depuis l’état q₀ avec l’entrée 0 dans l’automate A₁ : vers l’état q₁. Dans l’automate A₂, la transition depuis p₀ avec un 0 mène à l’état p₁. On écrit donc ⟨q₁, p₁⟩ dans le tableau :

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Avec l’entrée 1, on obtient : pour l’automate A₁, on a δ₁(q₀, 1) = q₂ et pour l’automate A₂, on a δ₂(p₀, 1) = p₀. On obtient donc l’état ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Complétons le reste du tableau :

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

Et d’après ce tableau, il ne reste qu’à dessiner le reste du diagramme.

On peut vérifier que l’automate fonctionne comme prévu. Essayons d’accepter le mot 0100. L’automate passe successivement par les états

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Comme l’état ⟨q₂, p₁⟩ est final, l’automate A accepte le mot 0100. Que se passerait-il si l’on essayait d’accepter le mot 0100 avec les automates A₁ et A₂ ? L’automate A₁ passerait successivement par ces états :

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

L’automate a fini dans l’état q₂, qui n’est pas final, donc l’automate A₁ n’accepterait pas ce mot. Et l’automate A₂ ?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

L’état p₁ est final, donc l’automate A₂ accepterait le mot 0100. Remarque que les automates A₁ et A₂ ont fini dans les états q₂ et p₁, ce qui est cohérent avec le fait que l’automate A a fini dans l’état ⟨q₂, p₁⟩.

Méthode avec un automate non déterministe

Exemple

On peut aussi démontrer que l’ensemble des langages réguliers est stable par réunion en construisant un automate non déterministe, bien plus simple.

Nous avons donc deux langages réguliers L₁, L₂ et nous voulons démontrer que leur réunion L = L₁ ∪ L₂ est aussi un langage régulier. Comme L₁, L₂ sont réguliers, il existe des automates A₁, A₂ qui acceptent ces langages. C’est-à-dire que L(A₁) = L₁ et L(A₂) = L₂. À l’aide de ces automates, nous construisons un automate A qui accepte le langage L, c’est-à-dire L(A) = L.

Supposons que les automates finis A₁ et A₂ ressemblent à ceci :

Pour obtenir un automate qui accepte la réunion des deux langages, on crée un nouvel état initial et, depuis cet état, on trace deux ε-transitions vers les anciens états initiaux. C’est tout. L’automate ressemblerait à ceci :

Formalisation

Nous avons deux automates A₁ = (Q₁ ; Σ ; δ₁ ; q₁ ; F₁) et A₂ = (Q₂ ; Σ ; δ₂ ; q₂ ; F₂). Nous construisons l’automate A = (Q ; Σ ; δ ; q₀ ; F) qui accepte la réunion des langages acceptés par les automates précédents, c’est-à-dire L(A) = L(A₁) ∪ L(A₂). On a alors :

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

Et nous définissons la fonction de transition δ ainsi :

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & si & q \in Q_{1} \\ δ_{2} (q, a) & si & q \in Q_{2} \\ {q_{1}; q_{2}} & si & q = q_{0} \land a = ε \\ \emptyset & si & q = q_{0} \land a \neq ε \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: Propriétés de clôture des langages réguliers

Suivant: Intersection de langages réguliers »