Intersection de langages réguliers

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

Idée de la démonstration

Nous avons deux langages réguliers L₁ et L₂ et nous voulons démontrer que leur intersection L₁ ∩ L₂ est encore 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 acceptera le langage L₁ ∩ L₂, ce qui prouvera que le langage L₁ ∩ L₂ est régulier.

Un mot appartient à l’intersection de deux langages s’il appartient à L₁ et à L₂ à la fois. Il faut donc que l’automate A₁ accepte le mot, et que l’automate A₂ l’accepte aussi. Nous utilisons exactement la même idée que pour la réunion de langages réguliers, en changeant seulement l’ensemble des états finals.

Formalisation de la méthode

Nous avons deux automates

$\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 l’automate A = (Q ; Σ ; δ ; q ; F) qui accepte le langage L(A₁) ∩ L(A₂). On a

Q = Q₁ × Q₂
Σ= Σ₁ ∩ Σ₂
q = ⟨q₀, p₀⟩
F = F₁ × F₂

Pour la fonction de transition δ, on a la relation suivante :

$\forall q \in Q_{1}, p \in Q_{2} : δ (⟨ q, p ⟩, a) = ⟨ δ_{1} (q, a), δ_{2} (p, a) ⟩$

Exemple

Soit l’automate A₁ suivant, qui accepte tous les mots contenant un nombre pair de 1 :

et l’automate A₂, qui accepte les mots contenant un nombre impair de 0 :

Nous construisons un automate qui acceptera l’intersection de ces langages. L’ensemble des états de cet automate est Q = Q₁ × Q₂, l’état initial est ⟨q₀, p₀⟩ et les états finals sont F₁ × F₂ :

Nous ajoutons ensuite les transitions selon la règle δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩ :

Dans cet automate, il y a par exemple, depuis l’état ⟨q₀, p₀⟩, une transition pour la lettre 0 vers l’état ⟨q₀,p₁⟩. Cela signifie que l’automate A₁ a, depuis l’état q₀, une transition pour la lettre 0 qui revient vers q₀. L’automate A₂, lui, a pour la lettre 0 une transition de l’état p₀ vers l’état p₁.

On peut tester cet automate. Il doit accepter des mots comme 110 ou 00000 (ils contiennent un nombre pair de 1 et un nombre impair de 0), mais il ne doit pas accepter des mots comme 11, 111, 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: Réunion de langages réguliers

Suivant: Différence de langages réguliers »