Atomate fini déterministe bidirectionnel

En informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel souvent abrégé en 2AFD, 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.

Texte : extrait de l'article Wikipédia « Automate fini déterministe bidirectionnel », sous licence CC BY-SA 4.0.