Ê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 déterministe
Résumé
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 contre-part 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.
Un alphabet est, dans ce contexte, tout ensemble fini, non vide.
Les éléments de sont appelés lettres.
Un mot est une suite finie d'éléments de ; la longueur d'un mot est le nombre d'éléments qui le composent. Un mot est noté par la juxtaposition de ses lettres. Ainsi, on écrit « oui » plutôt que « (o,u,i) ». Le mot vide, noté souvent , est l'unique mot de longueur zéro, composé d'aucune lettre. L'ensemble des mots sur est noté .
La concaténation de deux mots, notée ou plus simplement par juxtaposition, est définie pour deux mots et par . On a , la concaténation est associative : , par conséquent est un monoïde.
Un automate fini est un quintuplet , où :
est un alphabet,
est un ensemble fini, appelé ensemble des états,
est une partie de appelée ensemble des transitions,
est une partie de appelée ensemble des états initiaux,
est une partie de appelée ensemble des états finaux.
Un automate est déterministe si, d'une part, il a un et un seul état initial et si, d'autre part, la relation est fonctionnelle au sens suivant :
si et , alors .
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.