Automate fini déterministe bidirectionnel

En informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel (en anglais ) 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. 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. 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (5)

Cours associés (4)

Séances de cours associées (40)

Automate fini déterministe bidirectionnel

Automate fini alternant

En informatique théorique, et notamment en théorie des automates, un automate fini alternant est une extension des automates finis. Dans un automate fini non déterministe usuel, un mot est accepté si, parmi les états atteints, il y a au moins un état final. Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation.

Automate fini déterministe

Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.

CS-251: Theory of computation

This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica

EE-110: Logic systems (for MT)

Ce cours couvre les fondements des systèmes numériques. Sur la base d'algèbre Booléenne et de circuitscombinatoires et séquentiels incluant les machines d'états finis, les methodes d'analyse et de syn

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

Machines à états finis: bases et conception EE-110: Logic systems (for MT)

Introduit des machines à états finis, couvrant les bases, la conception et les applications pratiques telles que les décodeurs et les encodeurs.

Automata fini : DFA à Expression régulière

Explique la transformation dun DFA à une expression régulière et discute des concepts importants dans la théorie des automates.

Correction d'erreur d'orthographe

Explore la correction d'erreurs orthographiques, y compris les néologismes et les emprunts, en utilisant la distance d'édition et les automates à états finis.