Caractères de divisibilité et automates finis

Je suis depuis longtemps fasciné par les relations liant les propriétés mathématiques d’un ensemble de nombres aux propriétés syntaxiques de leurs représentations dans un système de numération donné.

Je trouve pour le moins intrigant que des propriétés morphologiques de mots soient caractéristiques de propriétés arithmétiques des entités abstraites qu’ils symbolisent.

Un exemple très simple, mais frappant, est la caractérisation des nombres pairs en base 10 : ce sont ceux dont l’écriture se termine par une des lettres 0,2,4,6,8, ou celle des multiples de 5 qui, en base 10 de nouveau, sont les nombres dont l’écriture s’achève par 0 ou 5. A priori la propriété « Le mot se termine par telle ou telle lettre » n’est pas de nature arithmétique. Nul besoin de savoir ce qu’est un nombre pour l’envisager — on pourrait même dresser un animal à la détecter — et pourtant elle permet de reconnaître si un nombre est pair ou multiple de 5.

L’étude des systèmes de numération est un vaste domaine de recherche auquel j’ai eu la chance de contribuer un peu ces dernières années. Je lui consacrerai de temps à autre quelques billets.

Pour commencer, je vais résoudre le problème posé dans le billet précédent par une méthode dont la portée dépasse de très loin la question initiale(*). Elle nous permettra de nous convaincre, ultérieurement, que tous les caractères de divisibilités peuvent être formulés en termes purement syntaxiques : il existe pour chaque diviseur d et chaque base b, une forme qui caractérise les représentations en base b des multiples de d(**).

Cela dit, cette forme est souvent relativement compliquée et ne débouche pas directement sur un critère praticable « à la main ». Mêmes s’ils en expriment certaines propriétés, les caractères de divisibilités usuels ont une autre origine, à savoir la distribution de la suite des résidus modulo d des puissances de la base b (voir à ce propos cette ressource). Par exemple, les puissances de 10 ayant toutes 1 pour reste de la division par 3, un nombre exprimé en base 10 a même reste modulo 3 que la somme de ses chiffres. Ici, le critère est récursif et consiste à remplacer le nombre étudié par un plus petit et à recommencer avec ce dernier jusqu’à tomber sur un chiffre.

Venons-en à notre question, à savoir prouver que les nombres dont l’écriture en base 2 est de la forme

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

sont divisibles par 3.

Nous allons pour cela construire un (multi-)graphe orienté. Il a trois sommets, notés 0,1,2, et, de chaque sommet partent deux arcs, d’étiquettes 0,1. On construit ces arcs conformément à la règle suivante : l’arc de label c issu du sommet de nom r aboutit au sommet dont le nom est le résidu de 2r+c modulo 3. Voici une représentation de ce graphe :

automate_1

L’écriture u_1\cdots u_s en base 2 d’un entier (positif) n décrit un chemin du graphe. L’origine du chemin est le sommet 0 (c’est pourquoi on a dessiné une petite flèche pointant sur ce dernier) et les étiquettes des arcs successifs dont il est composé sont les chiffres u_1,u_2,... (dans cet ordre). Par exemple, la représentation 110101 de 53 nous fait successivement passer par les sommets 0,1,0,0,1,2,2.

Par construction, le chemin associé à n aboutit au sommet dont le nom est le reste de la division de n par 3. Cela résulte facilement du fait que si v_1\cdots v_t est la représentation en base 2 d’un entier m alors v_1\cdots v_{t+1} est celle de 2m+v_{t+1}.

En conséquence, les multiples de 3 sont les nombres dont les représentations en base 2 décrivent un chemin du graphe qui aboutit en 0 (c’est pour cette raison que ce sommet est entouré par un trait double ci-dessus). C’est manifestement le cas des nombres dont la représentation est de la forme (1). Cela dit, il y en a d’autres. Par exemple les suites formées d’un nombre pair de 1, ou encore celles obtenues en juxtaposant plusieurs suites de la forme (1) séparées par des nombres arbitraires de 0, etc. La détermination de toutes les suites possibles — de leur forme générale — est une question sur laquelle je reviendrai plus tard.

Un des intérêts de la méthode utilisée ici est qu’elle s’adapte sans difficulté à toute base b et tout diviseur d.

Le graphe correspondant possède d sommets, un par reste r de la division par d; de chaque sommet partent b arcs, un par chiffre c, construit selon le principe résumé par la figure suivante (le bleu indique les résidus modulo d) :

automate_2

Les expressions en base b des nombres entiers décrivent des chemins d’origine 0 de ce graphe qui aboutissent aux restes modulo d des nombres. En particulier, pour les multiples de d, ces chemins se referment en 0.

Voici une représentation du graphe correspondant à la base 3 et au diviseur 5 :

automate_3

Les graphes dont il a été question ici sont des exemples d’automates finis. Ce sont des graphes particuliers qui servent à décrire des ensembles de mots, ceux qu’on obtient en juxtaposant les étiquettes des arcs des chemins d’origines et d’extrémités prescrites. Chaque automate se voit ainsi associer un ensemble de mots caractérisés par une syntaxe spécifique. La description de celle-ci est l’objet d’un beau théorème sur lequel je reviendrai : le théorème de Kleene.

Les automates sont particulièrement simples à implémenter. Aussi sont-ils énormément utilisés dans de nombreux domaines, en particulier dans les langages de programmation et les logiciels de traitement de texte.
__________
(*) C’est une méthode classique qu’on rencontre dans nombre de livres consacrés aux langages formels. On y pense d’ailleurs assez volontiers une fois baigné dans le contexte des automates finis.
(**) Ceci s’étend à des systèmes de numération plus généraux que les systèmes classiques de numération de position en base entière. J’y reviendrai peut-être plus tard.

Une réflexion sur “Caractères de divisibilité et automates finis

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