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:
- Give DFA's accepting the following languages over the alphabet {0,1}. The set of all strings that, when interpreted as a binary integer, is a multiple of 5.
- Draw the DFA capable of recognizing the set of all strings beginning with a 1 which interpreted as the binary representation of an integer (assuming the last digit to be processed is the least significant) is congruent to zero modulo 3 i.e., the numeric value of this binary representation is a multiple of 3.
- Construct the DFA that recognizes the language composed of all bits strings that begin with a 1 and which is congruent to zero modulo 5 when interpreted as the binary representation of an integer (Hopcroft and Ullman, 1979).
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é):
- X mod 3 = 0; (état acceptant)
- X mod 3 = 1;
- X mod 3 = 2.
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.
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:
- 12 mod 112 = 1, donc transition vers s1 sur lecture d'un 1;
- 02 mod 112 = 0, donc transition vers s0 sur lecture d'un 0.
On obtient alors le diagramme de transition ci-dessous.
En poursuivant la lecture de l'état s1, on a:
- 112 mod 112 = 0, donc transition vers s0 sur lecture d'un 1;
- 102 mod 112 = 2, donc transition vers s2 sur lecture d'un 0.
On obtient alors le diagramme de transition ci-dessous.
En poursuivant la lecture de l'état s2, on a:
- 1012 mod 112 = 2, donc transition vers s2 sur lecture d'un 1;
- 1002 mod 112 = 1, donc transition vers s1 sur lecture d'un 0.
On obtient alors le diagramme de transition ci-dessous.
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:
- X mod 5 = 0; (état acceptant)
- X mod 5 = 1;
- X mod 5 = 2;
- X mod 5 = 3;
- X mod 5 = 4.
En débutant la lecture de l'état s0, on a:
- 12 mod 1012 = 1, donc transition vers s1 sur lecture d'un 1;
- 02 mod 1012 = 0, donc transition vers s0 sur lecture d'un 0.
On obtient alors le diagramme de transition ci-dessous.
En poursuivant la lecture à partir de l'état s1, on a:
- 112 mod 1012 = 3, donc transition vers s3 sur lecture d'un 1;
- 102 mod 1012 = 2, donc transition vers s2 sur lecture d'un 0.
On obtient alors le diagramme de transition ci-dessous.
En poursuivant la lecture à partir de l'état s2, on a:
- 1012 mod 1012 = 0, donc transition vers s0 sur lecture d'un 1;
- 1002 mod 1012 = 4, donc transition vers s4 sur lecture d'un 0.
On obtient alors le diagramme de transition ci-dessous.
En poursuivant la lecture à partir de l'état s3, on a:
- 1112 mod 1012 = 2, donc transition vers s2 sur lecture d'un 1;
- 1102 mod 1012 = 1, donc transition vers s1 sur lecture d'un 0.
On obtient alors le diagramme de transition ci-dessous.
En poursuivant la lecture à partir de l'état s4, on a:
- 10012 mod 1012 = 4, donc transition vers s4 sur lecture d'un 1;
- 10002 mod 1012 = 3, donc transition vers s3 sur lecture d'un 0.
On obtient finalement le diagramme de transition ci-dessous.
