Automate fini déterministe
type d'automate fini associant une unique sortie à chaque entrée possible / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Automate fini déterministe?
Résumez cet article pour un enfant de 10 ans
Pour des articles plus généraux, voir Automate fini, Automate fini non déterministe et Théorie des automates.
Pour les articles homonymes, voir AFD.
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é.
Les automates finis déterministes ont plusieurs aspects avantageux : simplicité de leur définition, facilité de manipulation, aisance de la programmation informatique, élégance des propriétés mathématiques. Leur inconvénient majeur est la taille, mesurée en nombre d'états, qui peut dans certains cas être exponentielle par rapport à leur contrepartie non déterministe. Les deux classes d'automates finis, les automates finis déterministes et non déterministes, ont la même puissance d'expression : elles reconnaissent la même famille de langages, à savoir les langages rationnels, appelés aussi langages réguliers ou langages reconnaissables.