Critère de non régularité

On présente ici un critère de non régularité sur les langages. Autrement dit, on s’intéresse à une propriété sur les langages impliquant que ces derniers ne peuvent être reconnus par un automate fini. Cet exercice permet d’avoir une bonne introduction aux résiduels.

Exercice

Soit $\mathcal{L}$ un langage. Soit $(u_i)_{i \in \mathbb{N}}$ une suite infini de mots.

$1)$ Montrer que si pour tout couple $i,j$ il existe un mot $m$ tel que $u_im$ soit dans $\mathcal{L}$ et $u_jm$ ne le soit pas, alors $\mathcal{L}$ n’est pas un langage régulier.

$2)$ En déduire que $L = {\,a^{n}b^{n} \;|\; n \in \mathbb{N}}$ n’est pas régulier.

---

Correction

$1)$ Notre preuve se base sur l’idée suivante : on considère un automate déterministe $A$, un de ses état $q$ et deux mots $v$ et $w$ tel que lire $v$ ou $w$ nous emmène dans l’état $q$. Pour tout mot $x$, on a $vx$ et $wx$ termine dans le même état de $A$. Autrement dit $vx$ est reconnu par $A$ si et seulement si $wx$ est reconnu par $A$.

Ainsi, soit un automate $\mathcal{A}$ qui reconnaît notre langage $\mathcal{L}$. Soit $u_i$ et $u_j$ deux mots de notre suite. Si on termine dans le même état après avoir lu $u_i$ ou $u_j$, cela signifie que pour tout mot $x$ on a $u_ix$ appartient à $\mathcal{L}$ si et seulement si $u_jx$ appartient à $\mathcal{L}$. Or on sait que ce n’est pas le cas. De ce fait, après lecture de chaque mot de $(u_n)_{n\in\mathbb{N}}$ on arrive dans un état différent de $\mathcal{A}$. Cela implique que $\mathcal{A}$ a une infinité d’état, ce qui est absurde.

Ainsi, $\mathcal{L}$ n’est pas un langage régulier.

---

$2)$ On s’intéresse à la suite des $(u_{i})_{i \in \mathbb{N}}$ où pour tout $i$, $u_i = a^{i}$. Pour tout $i \neq j$ on a $a^{i}b^{i}$ appartient à $L$ mais $a^{j}b^{i}$ n’appartient pas à $L$. Par notre proposition précédente, il en résulte que $L$ n’est pas régulier.