Langages non réguliers

Au chapitre précédent, nous avons étudié les langages réguliers. Nous avons en particulier montré que les langages réguliers sont exactement les langages acceptés par les automates finis. Ainsi, le problème de décision $\omega \in L$ peut être résolu par un automate fini uniquement si $L$ est un langage régulier. Se pose donc la question de l'existence de langages non réguliers. Nous allons tout d'abord montrer l'existence de tels langages, puis nous donnerons une condition nécessaire pour qu'un langage soit régulier. La négation de cette condition nécessaire donne une condition suffisante pour qu'un langage ne soit pas régulier, et donc un moyen de prouver l'irrégularité.

Existence de langages non réguliers

Nous montrons maintenant qu'il existe strictement plus de langages qu'il n'existe de langages réguliers. L'ensemble des langages et l'ensemble des langages réguliers sont tous deux infinis. Nous introduisons donc dans un premier temps les outils permettant de comparer la taille de deux ensembles infinis.

Soient deux ensembles $A$ et $B$ et $f:A \rightarrow B$ une fonction de $A$ dans $B$. La fonction $f$ est une bijection si et seulement si :

• quels que soient $a,a' \in A$ avec $a\neq a'$, $f(a) \neq f(a')$ (injection) ;
• quel que soit $b \in B$, il existe $a \in A$ tel que $b=f(a)$ (surjection).

Une bijection définit une correspondance (association) entre les éléments de $A$ et de $B$, de telle façon que chaque élément de $A$ identifie un unique élément de $B$, et vice versa.

Un ensemble infini $A$ est dénombrable si et seulement s'il existe une bijection $f:A\rightarrow \mathbb{N}$ entre $A$ et l'ensemble des entiers naturels $\mathbb{N}$.

Un ensemble est donc dénombrable s'il est possible d'attribuer un numéro à chacun de ses éléments. Intuitivement, on peut énumérer les éléments d'un ensemble dénombrable, bien qu'il soit infini. Il y a donc un premier élément, et tout élément admet un élément suivant.

Lemme

L'ensemble $\Sigma^\ast$ des mots sur un alphabet $\Sigma$ est dénombrable (preuve page 33 du polycopié).

Puisque l'ensemble des mots sur un alphabet fixé est dénombrable, l'ensemble des expressions régulières sur $\Sigma$ est lui aussi dénombrable. En effet, une expression régulière sur $\Sigma$ est un mot sur l'alphabet fini $\Sigma \cup \{\varnothing, \epsilon,+,\star,(,)\}$.

Lemme

L'ensemble des parties d'un ensemble dénombrable n'est pas dénombrable.

Nous déduisons alors des deux lemmes précédents qu'il existe des langages non réguliers. Ils ne sont donc pas acceptés par des automates finis (mais éventuellement par des machines plus puissantes). Ils ne sont pas non plus représentables par des expressions régulières.

Théorème

Il existe des langages qui ne sont pas réguliers.

Par le premier lemme, nous savons qu'il existe un nombre dénombrable d'expressions régulières, puisqu'une expression régulière peut être vue comme un mot sur l'alphabet $\Sigma \cup \{\varnothing,\epsilon,+,\star,(,)\}$, où $\Sigma$ est un alphabet de symboles. De plus, nous savons qu'il y a au plus autant de langages réguliers que d'expressions régulières, et donc que l'ensemble des langages réguliers est dénombrable. Par le deuxième lemme, l'ensemble des langages étant l'ensemble des parties de $\Sigma^\ast$, nous savons que l'ensemble des langages est non dénombrable. Par conséquent, certains langages ne sont pas réguliers.

Lemme de l'étoile

Il existe donc des langages qui ne sont pas réguliers, et il n'existe pas de méthode générale pour décider si un langage quelconque est régulier. Cependant, nous exhibons maintenant une condition suffisante pour qu'un langage ne soit pas régulier.

1. Remarquons tout d'abord qu'un langage non régulier est nécessairement infini (tout langage fini est régulier).
2. Puisqu'un alphabet est fini, un langage infini contient des mots de longueur non bornée.
3. Tout langage régulier est accepté par un automate fini $A$. Soit $N$ le nombre d'états de $A$.
4. Tout mot $\omega$ appartenant à $\mathcal{L}(A)$ et tel que $|\omega| \geq N$ est reconnu par une exécution de $A$ qui passe au moins deux fois par le même état $q$ (elle visite $|\omega|+1 > N$ états). Le mot se décompose alors en $\omega = x.u.y$, où $u \neq \epsilon$ est lu sur la boucle de $q$ à $q$.
5. Par conséquent, le langage $x.u^\ast.y$ est inclus dans $\mathcal{L}(A)$ : il est possible de boucler autant de fois que souhaité sur l'état $q$ avant de se diriger vers $q_F$.

Ceci nous donne donc une condition nécessaire pour qu'un langage soit régulier : tout mot suffisamment long doit contenir un facteur qui peut être répété un nombre arbitrairement grand de fois. Ce n'est pas un moyen de prouver qu'un langage est régulier : la condition est nécessaire mais non suffisante. En revanche, cette méthode permet de prouver qu'un langage n'est pas régulier en montrant qu'il comporte (au moins) un mot qui ne respecte pas ce principe.

Théorème (lemme de l'étoile, pumping lemma)

Soient $L$ un langage régulier infini et $A=(Q,\Sigma,\delta,q_0,F)$ un automate fini déterministe tel que $L=\mathcal{L}(A)$. Pour tout mot $\omega \in L$ tel que $|\omega| \geq card(Q)$, il existe $x,u,y \in \Sigma^\ast$, tels que $u \neq \epsilon$ et $|x.u| \leq card(Q)$, vérifiant : $x.u.y=\omega$ et $\forall k \geq 0 , x.u^k.y \in L$.

Contraposée du théorème

Si pour tout entier $N>0$ il existe un mot $\omega \in L$ de longueur $|\omega| \geq N$ tel que, pour toute décomposition $\omega = x u y$ avec $|xu| \leq N$ et $u \neq \epsilon$, il existe $i \geq 0$ tel que $xu^iy \notin L$, alors $L$ n'est pas régulier.

Afin de prouver qu'un langage n'est pas régulier, nous falsifions le lemme de l'étoile. Intuitivement, il s'agit de prouver que, quel que soit l'automate fini $A$ considéré, celui-ci ne peut pas accepter $L$. Il n'est bien entendu pas possible d'examiner tous les automates finis, mais nous quantifions de la façon suivante :

• la taille de l'automate $A$ devient un paramètre de la preuve, et nous choisissons $\omega$ de telle sorte qu'il soit plus long que ce nombre d'états, afin de faire apparaître un cycle sur tout chemin acceptant $\omega$ dans $A$ ;
• d'autre part, la décomposition $\omega = x.u.y$ devient le second paramètre de la preuve. Nous considérons donc toutes les décompositions satisfaisant les contraintes sur $x$, $u$ et $y$, et nous exhibons un $k$ tel que $x . u^k . y \notin L$.

Le lemme de l'étoile, tel qu'énoncé ici, permet de montrer qu'il n'existe pas d'automate fini déterministe qui accepte un langage $L$ donné. Ceci ne suffit pas à prouver que $L$ n'est pas régulier. En effet, il pourrait exister un automate non déterministe qui accepte $L$. Nous verrons au chapitre 5 que ce n'est pas le cas : à tout automate non déterministe correspond un automate déterministe qui accepte le même langage.