Aller au contenu

Automate fini déterministe bidirectionnel

Un article de Wikipédia, l'encyclopédie libre.

En informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel (en anglais « two-way deterministic finite automaton ») souvent abrégé en 2AFD (en anglais 2DFA), est un automate fini déterministe qui peut relire des symboles d'entrée déjà vus. Comme pour les automates finis déterministes usuels, un 2AFD possède un nombre fini d'états, et le passage d'un état à un autre est régi par des transitions en fonction du symbole lu. De plus, une transition porte une information sur la direction de déplacement de la lecture, soit vers la droite soit vers la gauche. Un automate bidirectionnel peut donc être vu comme une machine de Turing qui ne peut pas écrire sur sa bande de données et qui ne dispose pas de mémoire auxiliaire.

Langages reconnus

[modifier | modifier le code]

Les automates finis déterministes bidirectionnels ont la même puissance de reconnaissance que les automates finis usuels. Par conséquent, les langages formels reconnus par les 2DFA sont exactement les langages rationnels. En revanche, un automate fini déterministe équivalent à un 2AFD donné peut avoir un nombre exponentiel d'états. Les 2AFD sont aussi équivalents aux machines de Turing qui ne peuvent écrire sur leur bande de données.

Description formelle

[modifier | modifier le code]

Les définitions formelles varient légèrement d'un auteur à un autre[1],[2],[3],[4]. Un automate fini déterministe bidirectionnel sur un alphabet est composé de :

  • un ensemble fini non vide d'états
  • un état initial
  • un ensemble d'états terminaux
  • une fonction de transition , où sont des indications de déplacement.

Il est parfois commode de supposer que l’entrée est encadrée par deux marqueurs qui délimitent la « véritable » donnée. L'automate commence son calcul sur le symbole le plus à gauche de l’entrée, ou sur le marqueur gauche. Quand il est dans l'état et lit le symbole , et si , il passe dans l'état et, selon que est ou , il continue sa lecture sur le symbole précédent, sur le symbole suivant, ou il reste sur le symbole lu. Une entrée est acceptée si après la lecture du symbole le plus à droite, ou lorsqu'il est sur le marqueur droit, il entre dans une configuration , où est état final. Il est possible qu'un automate boucle indéfiniment sur un état. Dans ce cas, l'entrée n'est pas acceptée. D'autres variations existent[2],[4].

Un exemple

[modifier | modifier le code]
Automate non déterministe à n+1 états reconnaissant le langage .

L'automate de la figure ci-contre est non déterministe. Il a états et reconnaît l'ensemble des mots sur l’alphabet binaire qui ont un en -ième position depuis la fin. Il est connu que tout automate fini déterministe reconnaissant ce langage a au moins états[4]. Un automate fini bidirectionnel déterministe à états existe pour ce langage, avec une constante. Il opère comme suit : dans une première passe, l'automate parcourt simplement le mot pour se positionner à droite de la dernière lettre ; puis, il lit le mot de la droite vers la gauche et vérifie que la lettre en -ième position est bien un . Pour cette phase, l'automate utilise n états. L'automate parcourt à nouveau la fin de l’entrée jusqu'à son bord droit, et se souvenant dans l'état si la lettre lue était un . Là le calcul se termine, dans un état d'acceptation ou de rejet selon la lettre lue. Ainsi, un gain exponentiel en place par rapport à un automate fini déterministe traditionnel est possible en autorisant un parcours bidirectionnel, et même un balayage simple au sens défini plus loin, où les changements de directions ne se font qu'aux bords de l'entrée.

Variantes du modèle

[modifier | modifier le code]

Plusieurs variantes des 2DFA sont considérés[4].

  • Les automates finis bidirectionnels non déterministes. Ce sont les mêmes automates, au déterminisme près.
  • Les automates à balayage (« sweeping automaton ») sont des automates bidirectionnels où les changements de direction ne sont autorisés qu'aux extrémités : l'automate lit le mot d'entrée de gauche à droite, puis de droite à gauche, etc. Ces automates bidirectionnels ont été nommés automates boustrophédon, en allusion à l'ancienne écriture grecque[5].
  • Automates à nondéterminisme extérieur (en anglais « outer nondeterministic automata »). Dans ces automates, un mouvement non déterministe est autorisé seulement quand la tête de lecture se trouve sur les symboles bordant l'entrée. Le comportement de l'automate est donc déterministe sur la donnée « réelle »[6].

Historique

[modifier | modifier le code]

La notion d'automate fini déterministe bidirectionnel est décrite dans l'article célèbre « Finite automata and their decision problems »[7] de Michael Rabin et Dana Scott de 1959 qui leur a valu le prix prix Turing en 1976. Rabin et Scott attribuent, dans leur article, la paternité de la démonstration de l’équivalence à entre 2DFA et automates finis déterministes à John C. Shepherdson. L'article de ce dernier paraît d'ailleurs dans le même numéro de la même revue[8].

En 1978, William J. Sakoda et Michael Sipser[9] posent la question du coût, en nombre d'états, de la simulation d'automates bidirectionnels non déterministes par des automates bidirectionnels déterministes. Ils conjecturent que ce coût est exponentiel. Malgré de nombreuses tentatives, la question est toujours ouverte[4].

Automate à pile bidirectionnel

[modifier | modifier le code]

Un automate à pile qui est autorisé de se déplacer dans les deux sens sur sa bande d'entrée est appelé un automate à pile bidirectionnel (en anglais « two-way pushdown automaton », abrégé en 2PDA)[10].

Cette famille a été étudiée par Hartmanis, Lewis et Stearns en 1965[11]. Aho, Hopcroft et Ullman[12] et Cook[13] donnent des caractérisations des langages reconnaissables par automate à pile bidirectionnel déterministe (2DPDA) et non déterministe (2NPDA). Gray, Harrison, et Ibarra étudient les propriétés de clôture de ces langages[14].

Transducteur fini bidirectionnel

[modifier | modifier le code]

Un transducteur fini bidirectionnel est un transducteur fini qui peut lire sur sa bande d'entrée dans les deux directions. Les transducteurs classiques (unidirectionnels) admettent des caractérisations par relations rationnelles et par des classes logiques. L'étude de leur version bidirectionnelle est moins avancée. Filiot et ses coauteurs ont étudié la simulation d’un transducteur bidirectionnel fonctionnel par un transducteur unidirectionnel[15],[16]. Une caractérisation algébrique des relations acceptées est connue lorsque les alphabets d’entrée et de sortie sont unaires. Elle a pour conséquence que les transducteurs bidirectionnel sont équivalents aux transducteurs à balayage ou « boustrophédon », où les changements de direction de la tête de lecture ne peuvent intervenir qu’au bord du mot d’entrée[17].

Automate quantique bidirectionnel

[modifier | modifier le code]

Le concept d'automate déterministe bidirectionnel a été généralisé en 1997 aux automates quantiques par Attila Kondacs et John Watrous[18]. Il est prouvé que ces machines peuvent reconnaitre des langages non réguliers et sont donc plus puissantes que les automates finis. Un autre article, par Andris Ambainis et John Watrous « Two-way finite automata with quantum and classical states » traite d'automates bidirectionnels à états mixtes, c'est-à-dire quantiques et classiques.

Notes et références

[modifier | modifier le code]
  1. ↑ Hopcroft et Ullman 1979.
  2. ↑ a et b Kozen 2006.
  3. ↑ Hing Leung.
  4. ↑ a b c d et e Pighizzini 2013.
  5. ↑ Cette terminologie se trouve notamment dans le cours de Marcel-Paul Schützenberger rédigé par Jean-François Perrot, ou dans l'article Jean-Pierre Pécuchet, « Automates boustrophédon et mots infinis », Theoretical Computer Science, vol. 35,‎ , p. 115-122 (DOI 10.1016/0304-3975(85)90009-x).
  6. ↑ Viliam Geffert, Bruno Guillon et Giovanni Pighizzini, « Two-Way Automata Making Choices Only at the Endmarkers », dans Adrian Horia Dediu & Carlos Martın-Vide (éditeurs), LATA, Springer Science + Business Media, coll. « Lecture Notes in Computer Science vol. 7183 », , 264–276 p. (DOI 10.1007/978-3-642-28332-1_23, arXiv 1110.1263).
  7. ↑ Rabin et Scott 1959.
  8. ↑ Shepherdson et 1959.
  9. ↑ Sakoda et Sipser 1978.
  10. ↑ Hopcroft et Ullman 1979.
  11. ↑ Richard E. Stearns, Juris Hartmanis et Philip M. Lewis II, « Hierarchies of memory limited computations », 6th Annual IIIE Symposium on Switching Circuit Theory and Logical Design (SWCT 1965), IEEE,‎ , p. 179–190 (DOI 10.1109/focs.1965.11).
  12. ↑ Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, « Time and tape complexity of pushdown automaton languages », Information and Control, vol. 13, no 3,‎ , p. 186-206 (DOI 10.1016/s0019-9958(68)91087-5).
  13. ↑ Stephen A. Cook, « Linear Time Simulation of Deterministic Two-Way Pushdown Automata », dans Proc. IFIP Congress, North Holland, , 75-80 p..
  14. ↑ James N. Gray, Michael A. Harrison et Oscar H. Ibarra, « Two-way pushdown automata », Information and Control, vol. 11, nos 1-2,‎ , p. 30-70 (DOI 10.1016/s0019-9958(67)90369-5).
  15. ↑ Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier et Frederic Servais, « From Two-Way to One-Way Finite State Transducers », 28th Annual Symposium on Logic in Computer Science (LICS), IEEE,‎ , p. 468-477 (DOI 10.1109/lics.2013.53).
  16. ↑ F. Baschenis, O. Gauwin, A. Muscholl et G. Puppis, « Untwisting two-way transducers in elementary time », 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS),‎ , p. 1–12 (DOI 10.1109/lics.2017.8005138, lire en ligne, consulté le )
  17. ↑ Christian Choffrut et Bruno Guillon, « An Algebraic Characterization of Unary Two-Way Transducers », Mathematical Foundations of Computer Science (MFCS) - 39th International Symposium, Springer Science + Business Media, lecture Notes in Computer Science, vol. 8634,‎ , p. 196-207 (DOI 10.1007/978-3-662-44522-8_17, lire en ligne).
  18. ↑ Attila Kondacs et John Watrous, « On the power of quantum finite state automata », Proceedings 38th Annual Symposium on Foundations of Computer Science, Institute of Electrical & Electronics Engineers (IEEE),‎ (ISBN 0-8186-8197-7, DOI 10.1109/sfcs.1997.646094, lire en ligne).

Bibliographie

[modifier | modifier le code]
  • Hing Leung, « Two-Way Deterministic Finite Automata », Department of Computer Science, New Mexico State University, Las Cruces, NM. — Exemples détaillés.
  • Michael Rabin et Dana S. Scott, « Finite automata and their decision problems », IBM Journal of Research and Development, vol. 3, no 2,‎ , p. 114–125 (DOI 10.1147/rd.32.0114).
  • John C. Shepherdson, « The reduction of two-way automata to one-way automata », IBM Journal of Research and Development, vol. 3, no 2,‎ , p. 198-200 (DOI 10.1147/rd.32.0198).
  • William J. Sakoda et Michael Sipser, « Nondeterminism and the size of two way finite automata », Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78, Association for Computing Machinery (ACM),‎ , p. 275–286 (DOI 10.1145/800133.804357).
  • John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley Publishing Company, , 418 p. (ISBN 978-0-201-02988-8), p. 124.
  • (en) Dexter C. Kozen, Theory of Computation, Londres, Springer Verlag, coll. « Texts in Computer Science », , xiv+418 (ISBN 978-1-84628-297-3, DOI 10.1007/1-84628-477-5, présentation en ligne)
  • Giovanni Pighizzini, « Two-Way Finite Automata: Old and Recent Results », Fundamenta Informaticae, vol. 126, nos 2-3,‎ , p. 225-246 (DOI 10.3233/FI-2013-879, arXiv 1208.2755) Document utilisé pour la rédaction de l’article
  • Semyon Petrov et Alexander Okhotin, « On the transformation of two-way finite automata to unambiguous finite automata », Information and Computation, vol. 295 « Selected papers of the 15th International Conference on Language and Automata Theory and Applications, LATA 2021 »,‎ , article no 104956 (DOI 10.1016/j.ic.2022.104956)

Articles liés

[modifier | modifier le code]
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Automate_fini_déterministe_bidirectionnel&oldid=210048726 ».