Caractères de divisibilité et automates finis II

Nous avions introduit dans ce billet un graphe avec lequel il est très aisé de reconnaître si un nombre, exprimé en base b, admet un reste donné r modulo d.

Nous avons appris depuis lors qu’il s’agit d’un automate fini déterministe. Il est construit sur l’alphabet \{0,...,b-1\} des chiffres en base b et ses états sont les restes \{0,...,d-1\} modulo d.

L’état initial est 0, le seul état final est r et il y a un arc d’origine p, d’extrémité q et de label a si, et seulement si, bp+a=q \mod d.

Par construction, la représentation u en base b d’un nombre(*) \overline u transforme l’état initial de cet automate en le reste de \overline u modulo d. En particulier, l’automate est accessible.

Désormais, nous ferons r=0 et nous noterons \mathcal A(b,d) l’automate en question. Il accepte exactement le mot vide et les mots de la forme 0^kuu est la représentation en base b d’un multiple entier, positif ou nul, de d.

Les automates \mathcal A (2,3) et \mathcal A (3,5) présentés dans le billet mentionné plus haut sont minimaux. L’automate \mathcal A(b,d) n’est cependant pas nécessairement minimal. Par exemple, l’automate minimal du langage accepté par \mathcal A(10,5) est

numeration_1

(Chaque arc de label « 0,5 » remplace deux arcs, un de label 0 et l’autre de label 5; de la même façon, celui de label « \neq 0,5 » représente autant d’arcs que de chiffres différents de 0 et de 5 en base 10.)

Le propos de ce billet est de prouver ceci :

L’automate \mathcal A(b,d) est minimal si, et seulement si, b et d sont premiers entre eux.

Une préoccupation plus ambitieuse serait de déterminer l’automate minimal acceptant le même langage que \mathcal A(b,d). C’est fait dans un article relativement récent que je mentionne plus bas ainsi que la formule donnant le nombre d’états de cet automate minimal qui y est obtenue. Naturellement, la propriété ci-dessus découle de cette formule. Nous allons cependant en donner ici une preuve directe : c’est facile tandis qu’établir la formule en question m’entraînerait trop loin.

Preuve, première partie

Supposons d’abord que b et d soient premiers entre eux et montrons que \mathcal A(b,d) est minimal. D’après le critère vu dans le billet précédent, comme il est accessible, cela revient à vérifier qu’il est réduit.

Soit un état i. Comme je l’explique plus bas, il existe un mot u tel que

\overline u = - b^{|u|}i \mod d

Ce mot est accepté depuis i mais n’est accepté depuis aucun autre état. De fait, soient un état j et la représentation v en base b d’un nombre congruent à j modulo d. On a j\cdot u=0\cdot vu. Par suite, u est accepté depuis j si, et seulement si, \overline{vu} est divisible par d. Comme

\overline{vu}=jb^{|u|}+\overline u=(j-i)b^{|u|} \mod d

cela arrive exactement quand j=i car b et d sont premiers entre eux.

Pour conclure cette première partie, il nous suffit donc de construire un mot u. Notons s la longueur de la représentation en base b de d-1 . La représentation u_0 en base b du reste de b^s(d-i) modulo d est de longueur au plus s. Le mot

u=0^{s-|u_0|}u_0

convient.

Preuve, seconde partie

Supposons à présent que le plus grand commun diviseur \delta de b et de d soit plus grand que 1 de sorte que

1<\frac{d}{\delta}+1<d

En particulier, r:=1+d/\delta est un état de \mathcal A(b,d). Comme bd/\delta est le plus petit commun multiple de b et d, b et br ont même reste modulo d et les arcs de même label issus de 1 et de r aboutissent au même état. Comme ils ne sont pas finals, les langages acceptés depuis 1 et r sont donc égaux. Ainsi, \mathcal A(b,d) n’est pas réduit et n’est donc pas minimal.

Dans l’article suivant :

B. Alexeev, Minimal DFA for testing divisibility, J. Comput. Syst. Sci. 69 (2004), 235–243.

on établit une formule donnant le nombre d’états(**) e(b,d) de l’automate minimal du langage accepté par \mathcal A(b,d). Elle s’exprime à l’aide de deux nombres associés à b,d. Le premier, n, est défini par la condition b^n<d\leq b^{n+1}. Le second, m, est le rang de l'élément à partir duquel la suite des plus grands communs diviseurs \mathrm{pgcd}(d,b^k), k\geq 0, se stabilise. Le nombre en question est

\frac{d}{\mathrm{pgcd}(d,b^{n+1})}+\sum_{0\leq t\leq \ell}\frac{b^t}{\mathrm{pgcd}(d,b^t)}

\ell est le plus petits des nombres(***) n,m-1.

On a par exemple e(10,5)=2 et il est clair que e(b,d)=d si b et d sont premiers entre eux. Je vous laisse vérifier la réciproque. 😉

__________
(*) Pour u=u_k\cdots u_0\in \{0,...,b-1\}^*, nous noterons |u|=k+1 la longueur de u et nous poserons

\overline u =\sum_{i=0}^ku_ib^i

Si u_k\neq 0, u est la représentation en base b du nombre \overline u.
(**) La notation e(b,d) n’a rien d’officiel. Elle est purement locale.
(***) Lorsque m=0, la somme n’apparaît pas, ou est considérée comme nulle.

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s