Automates finis déterministes reconnaissant les nombres binaires qui sont des multiples de n

Un usage intéressant des automates finis déterministes consiste à déterminer si un nombre binaire quelconque est un multiple de n.

Les livres sur les compilateurs contiennent d'ailleurs généralement une question demandant au lecteur de construire un tel automate pour une valeur de n donnée (souvent 3 ou 5). Quelques questions courantes:

Par contre, rares sont les livres faisant remarquer que les automates effectuant un tel travail présentent tous les mêmes caractéristiques, rendant triviale leur construction.

En effet, de tels automates associent toujours à chacun de leurs états le modulo n du nombre lu à cet état. Par exemple, un automate reconnaissant les entiers binaires qui sont des multiples de 3 aura exactement 3 états (le mot vide étant accepté):

L'état acceptant correspond toujours au modulo n = 0, c.-à.-d. que le nombre lu est un multiple de n.

Pour construire le diagramme de transition de l'automate, il suffit d'étudier l'effet qu'a la lecture d'un 1 ou d'un 0 sur le modulo du nombre lu à l'état courant. Il s'agit là d'une procédure totalement automatique. Les deux exemples ci-dessous illustrent la technique.

Automate fini déterministe reconnaissant les entiers binaires qui sont des multiples de 3

Voici la procédure pour construire un automate fini déterministe reconnaissant les entiers binaires qui sont des multiples de 3.

Premièrement, définir les états de l'automate: un pour chaque modulo tel que mentionné précédemment.

3 états de l'automate: s0, s1, s2.

Par la suite, il suffit de simuler une lecture partant de l'état s0 puis d'étudier son effet sur le modulo 3.

Ainsi, de l'état s0, on a:

On obtient alors le diagramme de transition ci-dessous.

Les transitions sortantes de l'état s0 sont toutes définies.

En poursuivant la lecture de l'état s1, on a:

On obtient alors le diagramme de transition ci-dessous.

Les transitions sortantes de l'état s1 sont toutes définies.

En poursuivant la lecture de l'état s2, on a:

On obtient alors le diagramme de transition ci-dessous.

Les transitions sortantes de l'état s2 sont toutes définies.

Automate fini déterministe reconnaissant les entiers binaires qui sont des multiples de 5

La même procédure, mais appliquée pour construire un automate fini déterministe acceptant les entiers binaires qui sont des multiples de 5.

Étant donné le multiple, l'automate aura 5 états:

3 états de l'automate: s0,s1,s2.

En débutant la lecture de l'état s0, on a:

On obtient alors le diagramme de transition ci-dessous.

Les transitions sortantes de l'état s0 sont toutes définies.

En poursuivant la lecture à partir de l'état s1, on a:

On obtient alors le diagramme de transition ci-dessous.

Les transitions sortantes de l'état s1 sont toutes définies.

En poursuivant la lecture à partir de l'état s2, on a:

On obtient alors le diagramme de transition ci-dessous.

Les transitions sortantes de l'état s2 sont toutes définies.

En poursuivant la lecture à partir de l'état s3, on a:

On obtient alors le diagramme de transition ci-dessous.

Les transitions sortantes de l'état s3 sont toutes définies.

En poursuivant la lecture à partir de l'état s4, on a:

On obtient finalement le diagramme de transition ci-dessous.

Les transitions de tous les états sont définies.