Probleme – Un automate qui compte modulo $k$

1. L'automate. Trois états, $0$, $1$, $2$ : l'état est le reste modulo 3 de ce qui a été lu. Initial $0$, acceptant $\{0\}$, et

$$\delta (q,c)=(2q+c)\mathrm{mod}3,$$

soit la table

Correction. Invariant : après lecture du préfixe $u$, l'état vaut $\mathrm{val}(u)\mathrm{mod}3$, où $\mathrm{val}(u)$ est l'entier écrit par $u$. Il est vrai au départ ($u=\epsilon$, $\mathrm{val}=0$). Il est conservé : lire un chiffre $c$ transforme $\mathrm{val}(u)$ en $2\mathrm{val}(u)+c$, et

$$(2\mathrm{val}(u)+c)\mathrm{mod}3=(2(\mathrm{val}(u)\mathrm{mod}3)+c)\mathrm{mod}3,$$

ce qui est exactement la transition. À la fin, l'état vaut $\mathrm{val}(w)\mathrm{mod}3$, et le mot est accepté si et seulement si ce reste est nul.

Vérification. L'automate a été exécuté sur les $16383$ mots de longueur au plus $13$, et sa réponse comparée au reste modulo $3$ de la valeur binaire calculée directement : accord complet. Les mots reconnus de longueur au plus $4$ sont $\epsilon$, 0, 00, 11, 000, 011, 110, 0000, 0011, 0110, 1001, 1100, 1111 — on y reconnaît $0,3,6,9,12,15$ et leurs écritures à zéros de tête.

2. L'expression. On élimine $1$, puis $2$. Les chemins de $0$ vers $0$ sont : ou bien un 0 direct ; ou bien un 1 vers l'état $1$, un séjour quelconque dans $\{1,2\}$, puis un retour en $0$. Le séjour se résume en $(\text{0}{\text{1}}^{\ast }\text{0}{)}^{\ast }$ — aller en $2$ par un 0, y boucler par des 1, revenir en $1$ par un 0 —, et le retour final se fait par un 1. D'où

$$\left(\text{0}\right|\text{1}(\text{0}{\text{1}}^{\ast }\text{0}{)}^{\ast }\text{1}{)}^{\ast }.$$

Cette expression a été évaluée par dérivées sur les $16383$ mots de longueur au plus $13$ et comparée à l'automate : accord complet.

3. La généralisation. L'automate se généralise sans changement : pour un diviseur $k$, on prend $k$ états — les restes — et $\delta (q,c)=(2q+c)\mathrm{mod}k$. L'invariant est le même mot pour mot. Il a été vérifié pour tout $k$ de $2$ à $16$ sur les mots de longueur au plus $12$ : accord complet.

Mais la minimalité, elle, ne se généralise pas, et c'est la surprise de la question. On mesure :

Pour $k$ impair, aucun état n'est superflu : $2$ est inversible modulo $k$, donc de deux restes distincts $r\ne r^{\prime }$ on tire $r{2}^L\ne r^{\prime }{2}^L$, et il existe un mot de $L$ bits qui complète $r$ en un multiple de $k$ sans compléter $r^{\prime }$. Les $k$ restes sont deux à deux distinguables.

Pour $k$ pair, non. Écrivons $k=2^{a}m$ avec $m$ impair. Dès qu'on a lu $L\ge a$ bits de plus, $r{2}^L\equiv 0(\mathrm{mod}{2}^a)$ : le reste modulo $2^a$ est oublié. Il ne reste à retenir que le reste modulo $m$, plus le nombre de bits déjà lus tant qu'il est inférieur à $a$. On mesure exactement $a+m$ états minimaux, et cette formule a été vérifiée sur les dix-huit valeurs $k=2,\dots ,16,20,24,32$ — par exemple $k=32=2^5$ donne $5+1=6$ états au lieu de $32$.

La leçon. Une construction naturelle et correcte n'est pas pour autant minimale, et rien dans l'écriture ne le signale. Il faut minimiser pour le savoir.

4. La question de fond. L'automate ne compte pas jusqu'à un entier arbitraire : il compte modulo $k$, et il n'y a que $k$ valeurs à retenir. C'est une information de taille bornée, indépendante de la longueur du mot — exactement ce qu'un automate fini peut se permettre.

La comparaison avec $\{a^n{b}^n\}$ éclaire le chapitre entier :

Ce n'est jamais « compter » qui est interdit à un automate fini, c'est retenir une quantité non bornée. Le lemme de l'étoile ne dit rien d'autre, et cette famille d'exemples montre qu'il ne faut pas le lire trop vite : un automate à trois états décide la divisibilité par $3$ d'un nombre arbitrairement grand.