Électronique Digérateur Science 2000+
Le oueblogue de #devroom@ulminfo.fr

Diviser avec sed

Divisibilité par sept

L’autre jour je me demandais comment déterminer la divisibilité d’un (grand) entier par sept, car je ne connais effectivement pas de critère de divisibilité simple pour ce nombre. Je retiendrai la première réponse à cette question sur math.SE : doubler le chiffre de poids faible et le soustraire du reste préserve la divisibilité par sept1. Mouais… Finalement je ne suis pas entièrement convaincu de l’efficacité de la méthode, ni celle des « graphes de divisibilité » dans la réponse suivante, par rapport à la méthode classique de la division posée. L’optimiste en moi répondra qu’une division par sept n’est pas si dure à poser mentalement de toute façon.

Algorithmiquement, à diviseur et base fixés, le calcul du reste d’une division euclidienne implémenté comme on le fait à l’école primaire a une complexité en temps linéaire, et en mémoire constante2. Donc la division est un automate.

Image d'automate
Automate reconnaissant les multiples de sept en base deux.

Or les langages reconnaissables par des automates forment une très jolie classe, riche par ses différentes caractérisations. Une d’elles me motive particulièrement.

Théorème de Kleene : un langage est reconnaissable si et seulement s’il est rationnel.

Pour rappel, les langages rationnels sont définis par des expressions dites rationnelles, dont les opérateurs sont :

  • la concaténation (le plus souvent implicite par juxtaposition, aussi ),
  • l’union (ici , aussi ou |)
  • et l’étoile de Kleene (ici , aussi ).
\begin{equation} LL' \define \{mm':m\in L, m'\in L'\}\\ L+L' \define L\cup L'\\ L^\star \define \{m_1\dots m_n:n\in\N; \forall i\in [1;n], m_i\in L\}\\ \end{equation}
Opérations rationnelles.

Un corollaire de ce théorème est que la classe des langages rationnels est, entre autres, close par intersection et passage au complémentaire. C’est une propriété non évidente du point de vue des expressions rationnelles, mais les opérations ensemblistes booléennes sont tout à fait triviales à effectuer sur des automates.

Le sens du théorème « rationnel reconnaissable » est le plus facile. On traduit par induction les trois opérations élémentaires sur les langages en opérations sur les automates3.

Le sens un peu moins évident dit que tout langage reconnaissable est défini par une expression rationnelle. Les expressions rationnelles, c’est simple. Donc on a un critère simple pour la divisibilité par n’importe quel entier, et on a un outil tout-fait pour l’implémenter! (Hum!)

La preuve

Le langage initial4 d’un état de l’automate est l’ensemble des mots qui partant d’un état initial mènent à l’état  :

Clairement, le langage reconnu par un automate est égal à l’union des langages initiaux de ses états acceptants  :

Remarque : dans un automate associé à une division (comme l’exemple ci-dessus), les langages initiaux sont les classes de congruence modulo . On construira une expression rationnelle pour chacun de ces langages puis on donnera le tout à sed, qui n’aura plus qu’à associer des nombres au bon motif. (Tout va comme sur des roulettes.)

Une transition () dans l’automate se traduit en une inclusion ; en prenant en compte toutes les transitions, on obtient des équations linéaires :

et vaut 5 si est un état initial, sinon.

\begin{array}{lcccccc}L_0&=&L_0\cat\mathtt{0}&\alt&L_3\cat\mathtt{1}&\alt&\mathtt{0}\\L_1&=&L_0\cat\mathtt{1}&\alt&L_4\cat\mathtt{0}&\alt&\mathtt{1}\\L_2&=&L_1\cat\mathtt{0}&\alt&L_4\cat\mathtt{1}&&\\L_3&=&L_1\cat\mathtt{1}&\alt&L_5\cat\mathtt{0}&&\\L_4&=&L_2\cat\mathtt{0}&\alt&L_5\cat\mathtt{1}&&\\L_5&=&L_2\cat\mathtt{1}&\alt&L_6\cat\mathtt{0}&&\\L_6&=&L_3\cat\mathtt{0}&\alt&L_6\cat\mathtt{1}&&\end{array}
Équations associées à l'automate dessiné ci-dessus.

Matriciellement, on a

Ou, avec des matrices augmentées,

cela se réécrit évidemment

Automate généralisé

Dans cette construction-là, les coefficients de la matrice sont des langages faits de mots à zéro ou une lettre. Au cours de la résolution, on aura aussi affaire à des systèmes avec des langages a priori quelconques pour coefficients de . Cette généralisation s’interprète automatiquement6; on peut penser à comme une matrice de transition, définissant un automate généralisé7 : un automate non déterministe où les transitions sont étiquettées non par des lettres mais par des langages; pour définir l’acceptation d’un mot lu en entrée, il faut alors deviner non seulement les transitions à suivre, mais aussi une factorisation adaptée du mot, chaque facteur devant appartenir au langage qui étiquette la transition correspondante.

L’algorithme décrit dans la suite peut être traduit en termes de transformations d’automates généralisés, ce qui donne l’algorithme de McNaughton et Yamada8.

Résolution d’une équation

On considère ici une seule équation linéaire de langages, de forme générale : \[X=X\Lambda+\Xi,\] d’inconnue , et paramètres et (éventuellement vides).

Dans le contexte d’un système linéaire, est une combinaison linéaire d’inconnues distinctes de et de coefficients de . Par exemple, dans , on a , , .

On résout :

\begin{align} X &=X\Lambda+\Xi\\
X(1-\Lambda)&=\Xi\\
X &=\Xi(1-\Lambda)^{-1}\\
\end{align}

/me chantonne. Développons…

\begin{align} X&=\Xi(1+\Lambda+\Lambda\Lambda+\Lambda\Lambda\Lambda+\dots)\\
X&=\Xi\Lambda^\star \end{align}

Ce pipeautage est une fausse preuve du vrai lemme d’Arden9, qui donne comme solution.

Cette solution est unique si et seulement si est sans mot vide; c’est le cas lorsque les équations décrivent des automates sans -transitions. Plus généralement, est toujours la plus petite solution au sens de l’inclusion. Dans tous les cas on peut montrer que par ce minimum on obtient bien les langages initiaux d’un automate10.

Pivot de Gauss

Le lemme d’Arden et la substitution sont les opérations de base qui permettent en fait d’exécuter un pivot de Gauss sur le système du pipeau suivant :

\[L(1-\Delta) = \I.\]

  • Une équation

    devient, par application du lemme d’Arden,

    Ça revient à normaliser le coefficient diagonal «  » de la -ème colonne11 de «  ».

  • Après cela, on réécrit l’équation

    on substitue dans une autre équation (pour )

    ce qui donne

    C’est l’addition d’un multiple, avec coefficient , de la -ème colonne à la -ème colonne de «  ».

La réduction termine après élimination de toutes les variables dans le membre de droite, quand . Le pivot de Gauss donne une solution linéaire en , qui se résume au produit par une matrice que l’on notera :

Les expressions rationnelles issues de la construction de peuvent dépendre de l’ordre dans lequel on résout les équations, mais les langages sous-jacents sont les mêmes.

On peut diviser avec sed

Sur ces idées, j’ai écrit un solveur d’équations linéaires de langages (prétexte à faire du JS), et un petit programme qui convertit le résultat et plus encore, une liste d’expressions rationnelles, en script sed : il lit un mot d’une ligne et répond avec le premier langage dans la liste qui contient la ligne d’entrée.

L’objectif de départ étant de faire des divisions, ici se trouve un script sed (0.5 Mo!) qui « calcule » le reste de la division de l’entrée en base dix par sept. D’autres exemples sont à trouver . Si vous tenez à calculer des divisions par votre nombre préféré à coup d’expressions rationnelles, la page du solveur a des boutons pour ça.

Ce qui me dépasse

Une implémentation naïve donne des expressions de tailles exponentielles en la taille du système. Y aurait-il des moyens pratiques de réduire la taille des expressions? Ou au contraire, peut-on montrer l’impossibilité de la tâche?

Généralisations dans d’autres structures que , comme les demi-anneaux et algèbres de Kleene12


  1. Parce que 7 divise 21, en bases , .

  2. C’est optimal quand possède un diviseur premier avec .

  3. Cette page dessine des automates reconnaissant le langage défini par les expressions rationnelles qu’on lui donne.

  4. En fait, dans mes cours j’ai plutôt vu défini le langage résiduel d’un état de l’automate : l’ensemble des mots qui en partant de (au lieu d’un état initial) mènent à un état acceptant. Le langage reconnu par un automate est égal à l’union des langages résiduels de ses états initiaux. On obtient aussi des équations linéaires, sauf que les « coefficients » sont à gauche des inconnues et un terme constant apparaît pour les états acceptants plutôt qu’initiaux. Mais dans le contexte de la reconnaissance de multiples, les langages initiaux associent un sens plus naturel aux états des automates, du moins lorsque l’on lit les nombres de gauche à droite.

    Les langages résiduels ou initiaux sont aussi utiles dans l’étude des automates minimaux (plus petits automates reconnaissant leur langage).

  5. , aussi noté car on est dans un semi-anneau. L’ensemble vide est lui noté .

  6. Il faut lire « automate-iquement » bien sûr.

  7. Appelation qui coïncide avec ce cours que j’ai trouvé par hasard, apparement dans un cursus de linguistique. On parle d’« extended automaton » dans le poly du cours 2.20.2 du MPRI (Fondations mathématiques de la théorie des automates)

    Ce type d’automate généralise les automates (non) déterministes, avec ou sans -transition… (Points de suspension du pipeau, c’est en fait tout ce que j’ai comme exemples.)

  8. Décrit succinctement dans le premier lien de la note précédente7. Pour plus de clarté, un algorithme dans le sens inverse est parfois attribué à ces mêmes noms; voir note 3.

  9. À faire proprement en exercice; points bonus pour une application du théorème de point fixe de Kleene. (Il est partout.)

  10. Une construction itérative des langages initiaux, en limitant le nombre de transitions parcourues depuis un état initial par exemple, créée un point fixe à la Kleene.

  11. Se rappeler que celui qui écrit ces lignes a décidé de tout transposer pour le confort de tous.

  12. Ce premier résultat Google pour la requête « matrix Kleene star » contient un autre exemple : dans l’algèbre min-plus, l’étoile de Kleene d’une matrice d’adjacence donne les longueurs des plus courts chemins entre les sommets!