Fini, donc régulier – mais l'automate grandit

1. $L_k$ est fini. Or tout langage fini est régulier : il s'écrit comme l'union finie des expressions dénotant chacun de ses mots. Ici $L_k$ dénote $\epsilon |ab|aabb|\cdots |a^k{b}^k$.

2. L'automate minimal compte $2k+2$ états. On les nomme par ce que l'automate doit retenir :

• après $a^i$ pour $0\le i\le k$ : il faut retenir $i$ — cela fait $k+1$ états, deux à deux distinguables puisque $a^i$ et $a^j$ se distinguent par le mot $b^i$ ;
• après $a^i{b}^j$ avec $1\le j\le i$ : il faut retenir le nombre $i-j$ de b encore attendus, soit $k$ états supplémentaires ;
• plus un puits, pour tout ce qui a déjà échoué.

On a construit pour chaque $k$ l'automate en arbre du langage puis minimisé : on mesure $4,6,8,10,12,14,16$ états pour $k=1,\dots ,7$, soit exactement $2k+2$.

3. $L$ n'est pas régulier, et l'on voit ici pourquoi le lemme de l'étoile aboutit. Chaque troncature $L_k$ est régulière, mais son automate minimal grandit sans borne. Un automate fixé, à $n$ états, ne peut donc reconnaître $L_k$ que pour $2k+2\le n$ : il y a toujours un $k$ trop grand pour lui. Formellement, le lemme conclut sur $u=a^n{b}^n$ : le facteur pompé $y$ ne contient que des a, et $x{y}^{2}z$ a plus de a que de b.

Ce qu'il faut retenir. « Régulier » n'est pas une propriété de chaque mot mais du langage entier. Toute partie finie d'un langage non régulier est régulière — cela n'apprend rien sur le langage. C'est la faute de raisonnement la plus fréquente sur ce chapitre.