Exercice 14.2 (corrigé de Michaël Périn)

On s´intéresse aux mots (qui correspondent à des entiers) qui valent 0 modulo a

Soit w un mot écrit en base 10.

Supposons que w correspond à l'entier k * a + r avec r < a

Concaténons le chiffre c à la fin du mot w, notée w.c,

Le mot w.c correspond alors à l'entier 10 * w + c = 10 * (k * a + r) + c = (10k) * a + 10 * r + c

la valeur modula a de w.c est celle de (10 * r + c) mod a

L'état r représente les mots qui correspondent à des entiers qui, modulo a, valent r

Les états de l'automate sont donc les restes dans la division par a soient 0, 1, …, a-1

La concaténation d'un chiffre c fait passer de l'état r à l'état (10 * r + c) mod a

Les transitions sont donc de la forme (r) —c—> (10*r+c mod a)

L'automate ne doit pas accepter epsilon et dans certains énoncés, on vous demandera même de ne pas accepter les 0 non significatifs (ceux à gauche du nombre).

Ainsi, "", "00", "000", … ne sont pas acceptés mais il ne faut pas perdre le "0".

Plusieurs facons de procéder :

• Puisque 6 = 2 * 3 (premiers), un mutiple de 6 est un multiple de 2 et un multiple de 3.

  Donc, on peut obtenir l'automate cherché en faisant le produit des automates: multiple₆ = multiple₂ x multiple₃.

• ou de façon directe en appliquant la méthode générale qui donne une solution équivalente.

Dans les deux cas certains états peuvent être regroupés par minimisation pour obtenir l'automate minimal.

Attention, 9 = 3 * 3 mais faire le produit de multiple₃ x multiple₃ donne le même automate : multiple₃.

Donc, on doit applique la méthode générale qui donne directement un automate minimal.

On peut toujours appliquer la méthode générale et on minimise pour avoir l'automate minimal.

On obtiendrait le même résultat si on avait remarqué qu'un multiple de 10 se termine nécessairement par un 0.

On applique la méthode générale et on minimise pour obtenir l'automate.

Soit on trouve une astuce comme pour 10.

Soit on applique la méthode générale, mais en programmant les algorithmes car ça devient fastidieux à la main.