Automate fini déterministe bidirectionnel

De testwiki
Aller à la navigation Aller à la recherche

En informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel (en anglais Modèle:Citation étrangère) 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

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

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

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

Un exemple

Automate non déterministe à n+1 états reconnaissant le langage A*aAn−1.

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

Variantes du modèle

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 (Modèle:Citation étrangère) 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 Modèle:Citation étrangère). 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

La notion d'automate fini déterministe bidirectionnel est décrite dans l'article célèbre Modèle:Citation étrangère[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

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 Modèle:Citation étrangère, 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

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]Modèle:,[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

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

Modèle:Références

Bibliographie

Articles liés

Modèle:Palette Automates finis et langages réguliers Modèle:Portail

  1. ↑ Modèle:Harvsp.
  2. ↑ 2,0 et 2,1 Modèle:Harvsp.
  3. ↑ Modèle:Harvsp.
  4. ↑ 4,0 4,1 4,2 4,3 et 4,4 Modèle:Harvsp.
  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 Modèle:Article.
  6. ↑ Modèle:Chapitre.
  7. ↑ Modèle:Harvsp.
  8. ↑ Modèle:Harvsp.
  9. ↑ Modèle:Harvsp.
  10. ↑ Modèle:Harvsp.
  11. ↑ Modèle:Article.
  12. ↑ Modèle:Article.
  13. ↑ Modèle:Chapitre.
  14. ↑ Modèle:Article.
  15. ↑ Modèle:Article.
  16. ↑ Modèle:Article
  17. ↑ Modèle:Article.
  18. ↑ Modèle:Article.
Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Automate_fini_déterministe_bidirectionnel&oldid=16071"