Cours d'approfondissement

Automates finis et applications

Responsable Jean-Eric Pin

Présentation du cours

Les automates finis constituent à la fois un modèle mathématique très utilisé en informatique et en automatique et une théorie riche et féconde. Sur le plan informatique, on retrouve les automates dans nombre d'algorithmes, notamment ceux de traitement de texte ou de compression de données. Ils interviennent dans les processus de compilation, de codage, dans l'étude des schémas de programme, dans la modélisation des circuits et du temps réel, en vérification, etc.. Il sont aussi utilisés en linguistique (analyse de texte), en mathématiques (groupes automatiques), en biologie (pour certains algorithmes liés au génome), dans l'étude des événements discrets en automatique. L'étude des automates, qui a été entreprise vers la fin des années cinquante, s'appuie sur des concepts mathématiques d'origines très diverses : algèbre non commutative, topologie, combinatoire, logique, etc. qui sont employés ici sur un mode rafraichissant. En bref, une théorie en pleine évolution riche de résultats surprenants. Ce cours d'approfondissement permettra à la fois de s'initier aux aspects fondamentaux de cette théorie et d'en découvrir certaines applications. On traitera les algorithmes fondamentaux sur les automates et on abordera ensuite les automates avec sortie, un modèle que l'on étudiera en particulier sur des exemples concrets (codage, addition, multiplication par une constante, etc.). Le cours sera enrichi par des projets soit de programmation, soit d'approfondissement d'articles de recherche.

Contenu du cours

Première partie: les gammes

Deuxième partie: automates avec sortie

Troisième partie: un aperçu de la théorie des automates

Prérequis pour ce cours

Quelques exemples d'automates

Exemple 1. Modélisation d'un jeu

Le joueur a les yeux bandés. Face à lui, un plateau sur lequel sont disposés en carré quatre jetons, blancs d'un côté et noirs de l'autre. Le but du jeu est d'avoir les quatre jetons du côté blanc. Pour cela, le joueur peut retourner autant de jetons qu'il le souhaite, mais sans les déplacer. A chaque tour, le maître de jeu annonce si la configuration obtenue est gagnante ou pas, puis effectue une rotation du plateau de zéro, un, deux ou trois quarts de tours. La configuration de départ est inconnue du joueur, mais le maître de jeu annonce avant le début du jeu qu'elle n'est pas gagnante. Chaque annonce prend une seconde, et il faut 3 secondes au joueur pour retourner les jetons. Pouvez-vous aider le joueur à gagner en moins d'une minute ?

10

Figure 1. Le plateau de jeu.

On va modéliser ce problème en utilisant des automates. A une rotation près, le plateau peut avoir six configurations différentes, représentées sur la figure 2. Seule la configuration 0 est gagnante.

10

Figure 2. Les différentes configurations.

Le joueur peut retourner un jeton, deux jetons adjacents, deux jetons opposés, trois jetons ou quatre jetons. Nous noterons respectivement 1, a, o, 3 et 4 ces différentes actions. Les transitions définies par ces actions sont représentées sur l'automate de la figure 3, dans lequel toutes les transitions arrivant sur la configuration gagnante ont été omises.
10

Figure 3. Les chemins interdits.

On peut tenir le raisonnement suivant: si on aboutit à la position 4, il suffit de retourner tous les jetons. Donc, si on a une stratégie gagnante pour le jeu G(0, 4) dans lequel on gagne dès que les quatre jetons sont de même couleur, on obtient une stratégie gagnante pour le jeu initial en intercalant une action 4 après chaque coup. On observe de la même façon que si on aboutit à la position o, retourner deux jetons opposés permet d'arriver dans l'une des configurations 0 ou 4, et donc de gagner G(0, 4). Par conséquent, si on a une stratégie gagnante pour le jeu G(0, o, 4) dans lequel les configurations 0, o et 4 sont gagnantes, on obtient une stratégie gagnante pour G(0, 4) en intercalant o après chaque coup. Observons encore que si on arrive dans la position a, on aboutit en 0, o ou 4 en jouant a, ce qui permet de gagner G(0, o, 4). Finalement, il suffit de jouer 1 pour gagner le jeu G(0, a, o, 4), car cette action change la parité du nombre de jetons. En résumé, on gagne avec le mot 4o4a4o414o4a4o4, qui est de longueur 15. Dans le cas le plus défavorable, il y aura donc 15 annonces du maître de jeu et le jeu prendra donc 15 + 3 x 15 = 60 secondes. Pour une approche plus systématique, il suffit de trouver le mot le plus court dans le complémentaire du langage reconnu par l'automate de la figure 3. Pour cela, on peut déterminiser cet automate, puis le compléter pour calculer le complément. Il reste à appliquer l'algorithme classique du plus court chemin entre deux sommets d'un graphe (ici l'état initial et l'unique état final) pour déterminer un mot de longueur minimale. On retrouve ainsi le mot 4o4a4o14o4a4o4, qui est l'unique solution.

Exemple 2. Multiplication par une constante.

Pour réaliser la multiplication par 5 d'un entier n, on utilise la représentation binaire inversée. Par exemple, le nombre 13, dont la représentation binaire est 1101, est ici codé 1011.

La multiplication par 5 est réalisée par l'automate de la figure 4. Le principe de fonctionnement est le suivant. On lit un mot d'entrée (on prendra comme exemple 1011) à partir de l'état initial, indiqué par une flèche entrante. Sur l'automate de la figure 4, l'état initial est l'état 1. On lit ensuite une à une les lettres du mot d'entrée. Pour chaque lettre lue (en bleu sur l'automate) on sort la lettre verte qui lui correspond (les lettres bleues et vertes sont séparées par une barre verticale sur la figure). Par ailleurs «on suit les flèches». Ainsi, si on lit 1, on sort 1 et on se retrouve dans l'état 3. Ensuite, on lit 0, on sort 0 et on arrive dans l'état 2. On lit ensuite 1, on sort 0 et on arrive dans l'état 4. On lit ensuite 1, on sort 0 et on arrive en 5. Lorsque la dernière lettre a été lue, on prend la flèche de sortie correspondant à l'état où l'on est arrivé (ici 5) et on sort le mot figurant sur cette flèche de sortie (ici le mot 001). Le mot de sortie est donc 1000001, qui code l'entier 65, qui est bien égal à 5 x 13...

L'un des buts de ce cours est de comprendre comment un tel automate peut-être obtenu sans tâtonnement...

10

Figure 4. Un automate réalisant la multiplication par 5.

Applications

Exemples de Projets

Démonstrations

En cours de réalisation...

Bibliographie

  1. A. V. Aho, J. E. Hopcroft et J. D. Ullman, The design and analysis of computer algorithms, Addison Wesley, 1974.

  2. A. V. Aho, R. Sethi et J. D. Ullman, Compilers - Principles, techniques, and tools, Addison Wesley, 1986.

  3. D. Beauquier, J. Berstel et P. Chrétienne, Éléments d'algorithmique, Masson, 1992.

  4. J. Berstel, Transductions and context-free languages, Teubner, 1979.

  5. J. Berstel et M. Morcrette, State complexity of finite-state devices, state compressibility and incompressibility, in Pixim 89: l'image numérique à Paris, A. Gagalowicz (éd.), Paris, 1989, pp. 387-395, Hermès.

  6. J. Berstel et D. Perrin, Theory of codes, Academic Press, 1985.

  7. J. Berstel et C. Reutenauer, Rational series and their languages, EATCS monographs in Computer Science, Springer, Berlin, 1988.

  8. J.-C. Birget, State complexity of finite-state devices, state compressibility and incompressibility, Mathematical Systems Theory 26 (1993), 237-269.

  9. D. Breslauer, The suffix tree of a tree and minimizing sequential transducers, Theoret. Comp. Sci. 191 (1998), 131-144.

  10. V. Bruyère, G. Hansel, C. Michaux et R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994), 191-238.

  11. V. Bruyère et C. Reutenauer, A proof of Choffrut's theorem on subsequential functions, Theoret. Comp. Sci. 215 (1999), 329-335.

  12. J. A. Brzozowski, Derivatives of regular expressions, Journal of the ACM 11 (1964), 481-494.

  13. J. A. Brzozowski et M. Yoeli, Digital Networks, Prentice Hall, Englewood Cliffs, N. J., 1976.

  14. C. Choffrut, Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles, Theoret. Comp. Sci. 5 (1977), 325-338.

  15. C. Choffrut, A generalization of Ginsburg and Rose's characterization of gsm mappings, in Automata, Languages and Programming, H. A. Maurer (éd.), pp. 88-103, Lecture Notes in Comput. Sci. vol. 71, Springer, 1979.

  16. J. H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, London, 1971.

  17. K. Culik II et J. Kari, Image compression using weighted finite automata, Computer and Graphics 16 (1987), 305-313.

  18. S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974.

  19. S. Eilenberg, Automata, Languages and Machines, vol. B, Academic Press, 1976.

  20. C. C. Elgot, Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc. 98 (1961), 21-52.

  21. C. C. Elgot et M. O. Rabin, Decidability and undecidability of second (first) order theory of (generalized) successor, J. of Symbolic Logic 31 (1966), 169-181.

  22. D. B. Epstein, J. Cannon, D. Hold, S. Levy, M. Paterson et W. Thurston, Word processing in groups, Jones and Barlett, Boston-London, 1992.

  23. J. Hartmanis et R. Stearns, Sets of numbers defined by finite automata, Amer. Math. Monthly 74 (1967), 539-542.

  24. J. Hopcroft et J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley, 1979.

  25. S. C. Kleene, Representation of Events in nerve nets and finite automata, in Automata Studies, C. Shannon et J. McCarthy (éd.), Princeton, New Jersey, 1956, pp. 3-42, Princeton University Press.

  26. D. Krob, Complete sets of B-rational identities, Theoret. Comp. Sci. 89 (1991), 207-343.

  27. J. Lagarias, The 3x+1 problem and its generalizations, Am. Math. Monthly, 1985, 3-23.

  28. M. Lothaire, Combinatorics on Words, Cambridge University Press, 1982.

  29. G. Mealy, A method for synthesizing sequential circuits, Bell System Technical J. 34 (1955), 1045-1079.

  30. E. Moore, Gedanken experiments on sequential machines, in Automata Studies, C. Shannon et J. McCarthy (éd.), Princeton, New Jersey, 1956, pp. 129-153, Princeton University Press.

  31. M. Perles, M. Rabin et E. Shamir, The theory of definite automata, IEEE. Trans. Electron. Comput. 12 (1963), 233-243.

  32. D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, J. van Leeuwen (éd.), vol. B : Formal Models and Semantics, ch. 1, Elsevier, 1990.

  33. D. Perrin et J.-E. Pin, Semigroups and automata on infinite words, in NATO Advanced Study Institute Semigroups, Formal Languages and Groups, J. Fountain (éd.), pp. 49-72, Kluwer academic publishers, 1995.

  34. D. Perrin et J.-E. Pin, Infinite Words, Princeton University Press, 1999. (à paraître, voir http://liafa.jussieu.fr/ ~ jep).

  35. J.-E. Pin, Varieties of Formal Languages, North Oxford Academic, London and Plenum, New York, 1986.

  36. J.-E. Pin, Finite semigroups and recognizable languages : an introduction, in NATO Advanced Study Institute Semigroups, Formal Languages and Groups, J. Fountain (éd.), pp. 1-32, Kluwer academic publishers, 1995.

  37. J.-E. Pin, Syntactic semigroups, in Handbook of language theory, G. Rozenberg et A. Salomaa (éd.), vol. 1, ch. 10, pp. 679-746, Springer Verlag, 1997.

  38. M. O. Rabin et D. Scott, Finite automata and their decision problems, Rap. Tech., IBM J. Res. and Develop., 1959. "Reprinted in Sequential Machines, E. F. Moore (ed.) , Addison-Wesley, Reading, Massachussetts, (1964), 63-91.".

  39. G. N. Raney, Sequential functions, JACM 5 (1958), 177-180.

  40. C. Reutenauer, Subsequential functions: characterizations, minimizations, examples, pp. 62-79, Lecture Notes in Comput. Sci. vol. 464, Springer, 1990.

  41. C. Reutenauer et M.-P. Schützenberger, Subsequential functions: characterizations, minimizations, examples, SIAM J. Comput 20 (1991), 669-685.

  42. M.-P. Schützenberger, Sur une variante des fonctions séquentielles, Theoret. Comp. Sci. 4 (1977), 47-57.

  43. H. Short, An introduction to automatic groups, in NATO Advanced Study Institute Semigroups, Formal Languages and Groups, J. Fountain (éd.), pp. 1-32, Kluwer academic publishers, 1995.

  44. W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science, J. van Leeuwen (éd.), vol. vol. B, Formal models and semantics, pp. 135-191, Elsevier, 1990.

  45. W. Thomas, Languages, Automata and Logic, in Handbook of language theory, G. Rozenberg et A. Salomaa (éd.), vol. 3, ch. 7, pp. 389-455, Springer Verlag, 1997.

  46. S. Yu, Regular languages, in Handbook of language theory, G. Rozenberg et A. Salomaa (éd.), vol. 1, ch. 2, pp. 679-746, Springer Verlag, 1997.


Page maintenue par Jean-Eric Pin. Les automates figurant sur cette page ont été réalisés à l'aide du programme LaTeX gastex
Dernière modification 1 juil 2001