Complémentaire d’un langage régulier

Soit un langage régulier L. Nous allons démontrer que le complémentaire du langage L est encore un langage régulier.

Qu’est-ce que le complémentaire

Le complémentaire d’un langage L, c’est l’ensemble de tous les mots qui ne sont pas dans L. On le note L'. Autrement dit, pour un alphabet Σ, on a :

$$L^{\prime }=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

Par exemple, pour le langage des mots contenant au moins une lettre 1, le complémentaire est le langage des mots qui ne contiennent aucune lettre 1.

Méthode

La méthode est très simple. Nous avons un langage régulier L et un automate complet déterministe A = (Q ; Σ ; δ ; q₀ ; F) qui l’accepte (tout automate fini peut être transformé en un tel automate). Pour obtenir l’automate A' qui accepte L', on échange les états finals et les états non finals : A' = (Q ; Σ ; δ ; q₀ ; Q ∖ F). C’est tout.

Exemple

Soit l’automate suivant :

L’automate qui accepte le complémentaire du langage ressemblerait à ceci :

Sources

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