Automate fini inambigu

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 .