Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Automate fini inambigu
Résumé
upright=1.5|thumb|Un automate fini inambigu à n+1 états reconnaissant les mots qui ont un a en position n depuis la fin. Un automate déterministe équivalent a au moins états
En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais , abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes langages formels, à savoir les langages réguliers.
Le nombre d'états d'un automate inambigu peut être exponentiellement plus petit qu'un automate déterministe équivalent. En contre-partie, certains problèmes sont plus difficiles à résoudre pour les automates inambigus que pour les automates déterministes. Par exemple, partant d'un automate A, un automate A' reconnaissant le complément du langage accepté par A se construit en temps linéaire si A est déterministe, mais il a été démontré qu'il ne peut être calculé en temps polynomial si A est inambigu.
La notion d'automate inambigu se généralise à d'autres modèles de machines ou de calcul. Un présentation générale a été donnée par Thomas Colcombet.
Un automate fini non déterministe , où est l'ensemble des transitions, l’ensemble des états initiaux et l'ensemble des états terminaux, est dit inambigu si, pour tout mot reconnu par l'automate, il existe un seul chemin réussi d'étiquette , donc un seul chemin
avec et .
Soit l'ensemble des mots sur l'alphabet binaire dont la lettre en position depuis la fin est un . Les figures ci-contre montrent un automate inambigu reconnaissant ce langage pour n=2, et un automate déterministe pour ce même langage.
L'automate déterministe minimal acceptant a états, alors que l’automate inambigu pour le même langage n'a que états.
On peut tester si un automate fini non déterministe à m transitions est inambigu en temps .
Source officielle
À 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.