Automate fini déterministe bidirectionnel

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.

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 ${\displaystyle A}$ est composé de :

• un ensemble fini non vide ${\displaystyle Q}$ d'états
• un état initial ${\displaystyle s}$
• un ensemble d'états terminaux ${\displaystyle T}$
• une fonction de transition ${\displaystyle \delta :Q\times A\rightarrow Q\times \{L,R,S\}}$, où ${\displaystyle L,R,S}$ 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 ${\displaystyle q}$ et lit le symbole ${\displaystyle a}$, et si ${\displaystyle \delta (q,a)=(p,D)}$, il passe dans l'état ${\displaystyle p}$ et, selon que ${\displaystyle D}$ est ${\displaystyle L,R}$ ou ${\displaystyle S}$, 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 ${\displaystyle (t,R)}$, où ${\displaystyle t}$ 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].

Automate non déterministe à n+1 états reconnaissant le langage ${\displaystyle A^{*}aA^{n-1}}$.

L'automate de la figure ci-contre est non déterministe. Il a ${\displaystyle n+1}$ états et reconnaît l'ensemble des mots sur l’alphabet binaire ${\displaystyle A=\{a,b\}}$ qui ont un ${\displaystyle a}$ en ${\displaystyle n-1}$-ième position depuis la fin. Il est connu que tout automate fini déterministe reconnaissant ce langage a au moins ${\displaystyle 2^{n}}$ états[4]. Un automate fini bidirectionnel déterministe à ${\displaystyle n+c}$ états existe pour ce langage, avec ${\displaystyle c}$ 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 ${\displaystyle n-1}$-ième position est bien un ${\displaystyle a}$. 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 ${\displaystyle a}$. 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.

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].

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].

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].

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].

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.

• 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, n^o 2,‎ avril 1959, 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, n^o 2,‎ avril 1959, 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),‎ 1978, 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, 1979, 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 », 2006, 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, n^os 2-3,‎ 2013, p. 225-246 (DOI 10.3233/FI-2013-879, arXiv 1208.2755)

• Automate fini déterministe
• Transducteur fini
• Automate quantique