Propriétés de clôture des langages réguliers

Un langage L est régulier si et seulement s’il existe un automate A qui accepte ce langage, c’est-à-dire L(A) = L. Nous allons démontrer que les langages réguliers sont stables par les opérations de réunion, d’intersection, de concaténation et d’étoile.

Stabilité d’un ensemble par une opération

On dit qu’un ensemble M est stable par une opération ⊗ si

$$\mathrm{\forall }x,y\in M:x\otimes y\in M$$

Un exemple est l’addition dans l’ensemble des entiers naturels. La somme de deux entiers naturels quelconques est de nouveau un entier naturel. En revanche, l’ensemble des entiers naturels n’est pas stable par soustraction, car par exemple 7 − 15 = −8 et −8 n’est pas un entier naturel.

Nous allons démontrer par quelles opérations l’ensemble des langages réguliers est stable. Toutes les démonstrations seront constructives, c’est-à-dire que nous construirons un automate qui accepte le langage obtenu.