Caractères de divisibilité et automates finis III

Pour illustrer ce que nous avons appris des langages réguliers, je vous propose de revenir un moment sur les caractères de divisibilité et d’achever ce que nous avions entamé ici.

Les représentations en base b des nombres entiers divisibles par d sont toutes acceptées par l’automate construit dans ce billet et que nous avons noté ultérieurement \mathcal A(b,d) .

Le langage accepté par cet automate comporte d’autres mots. En fait, il accepte le mot vide, et les mots de la forme 0^*uu est une des représentations en question. On pourrait le modifier afin de n’accepter que celles-ci. Cela le compliquerait un peu et ce n’est pas vraiment indispensable.

Nous savons désormais que le langage accepté par l’automate est régulier et qu’il est décrit par une expression régulière qui spécifie la forme générale de ses éléments. Nous sommes donc convaincus, à présent, que les caractères de divisibilités ont une caractérisation purement syntaxique ainsi que je l’avais annoncé dans le billet en question.

Nous avons également appris comment obtenir une telle expression régulière, en déterminant la solution minimale du système d’inéquations caractéristique de l’automate. Je vais illustrer cela pour les multiples de 3 en base 2.

Voici l’automate \mathcal A(2,3). J’y ai remplacé les chiffres 0 et 1 par les lettres a et b afin de ne pas créer de confusion avec le 0 des expressions régulières. Chaque état a pour nom un reste de la division par 3.

automate_32

Il est caractérisé par le système d’inéquations

\left\{\begin{array}{lcl}x_0&\geqslant&ax_0+bx_1+e\\x_1&\geqslant&ax_2+bx_0\\x_2&\geqslant&ax_1+bx_2\end{array}\right.

dont la solution minimale, obtenue par la méthode présentée ici, est

\left\{\begin{array}{lcl}x_0&=&(a+b(ab^*a)^*b)^*\\x_1&=&(ab^*a)^*b(a+b(ab^*a)^*b)^*\\x_2&=&b^*a(ab^*a)^*b(a+b(ab^*a)^*b)^*\end{array}\right.

Ainsi, les représentations en base 2 des multiples de 3 appartiennent au langage décrit par (dans les notations initiales, 0 représentant ici le chiffre zéro et non le langage vide)

\big(0+1(01^*0)^*1\big)^*

Il contient les mots de la forme

10\underbrace{1\cdots1}_{n_1}00\underbrace{1\cdots1}_{n_2}0\cdots0\underbrace{1\cdots1}_{n_p}01

qui se trouvent en effet dans 1(01^*0)^*1. Ce sont eux que j’ai utilisés il y a quelque temps pour formuler un petit exercice sur les multiples de 3 en base 2. Disons qu’ils sont du premier type, les suites de 0, suite vide comprise, étant du second type. Les représentations des multiples de 3 en base 2 sont alors, outre le mot 0, les mots de la forme

P_1Q_1P_2Q_2\cdots P_rQ_r

où les P_i sont du premier type, les Q_i sont du second type et où r\geqslant 1, afin qu’il y ait un 1 en tête de mot.

Si on voulait analyser la forme des représentations en base 2 des nombres congrus à k=1,2 modulo 3, on changerait l’état final de l’automate \mathcal A(2,3), en prenant k comme nouvel état final. Cela reviendrait à ôter le terme indépendant e de la première inéquation pour le placer dans la seconde ou dans la troisième, selon la valeur de k .

L’utilisation de l’automate \mathcal A(b,d) pour déterminer « à la main » le reste modulo d d’un nombre écrit en base b est assez commode lorsque la base et le diviseur sont petits, c’est-à-dire tant qu’il reste « dessinable ». Dans les autres cas, il pourrait encore être utilisé mais après avoir été implémenté dans un langage de programmation et éventuellement rendu minimal par un algorithme approprié.

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