Différence de langages réguliers

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

Idée

En réalité, il n’y a pas grand-chose à démontrer. Pour la différence de deux ensembles, on a en effet la relation suivante :

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

où L₂′ est le complémentaire du langage L₂. Grâce aux chapitres sur l’intersection de langages réguliers et sur le complémentaire d’un langage régulier, nous savons que les langages réguliers sont stables par ces deux opérations. Cela signifie que nous savons construire un automate qui accepte l’intersection de langages et le complémentaire d’un langage. Nous pouvons donc utiliser ces automates pour construire un automate qui acceptera le langage L₁ ∩ L₂′, qui est justement le langage L₁ ∖ L₂.

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 la différence de ces langages. Il nous faut pour cela un automate A₂′ qui soit le complémentaire de l’automate A₂. Il suffit d’échanger les états finals et les états non finals :

Il ne reste plus qu’à construire l’automate A qui acceptera l’intersection des langages L(A₁) et L(A₂′) :

Sources

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