Ê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 GraphSearch.
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.
Publications associées (3)
Filtering Random Graph Processes Over Random Time-Varying Graphs
Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deter
Institute of Electrical and Electronics Engineers2017Approximation for Problems in Multi-User Information Theory
The main goal in network information theory is to identify fundamental limits of communication over networks, and design solutions which perform close to such limits. After several decades of effort,
EPFL2010Combinatorial algorithms for wireless information flow
Christina Fragouli, Aurore Amaudruz
A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the net
2009Personnes associées (3)
Concepts associés (36)
Table de transition d'état
Dans la théorie des automates et en logique séquentielle, une table de transition d'état est un tableau montrant dans quel état (ou états dans le cas d'un automate fini non déterministe) d'un automate fini se déplacer, sur la base de l'état actuel et des autres entrées. Une table d'état est essentiellement une table de vérité, dans laquelle certaines des entrées sont l'état actuel, et les sorties comprennent l'état suivant, en même temps que les autres sorties.
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é.
Diagramme états-transitions
Un diagramme états-transitions est un schéma utilisé en génie logiciel pour représenter des automates déterministes. Il fait partie du modèle UML et s'inspire principalement du formalisme des statecharts et rappelle les grafcets des automates. S'ils ne permettent pas de comprendre globalement le fonctionnement du système, ils sont directement transposables en algorithme. En effet, contrairement au diagramme d'activité qui aborde le système d'un point de vue global, le diagramme états-transitions cible un objet unique du système.
Cours associés (22)
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
CIVIL-237: Safety and reliability
Ce cours comporte les notions de sécurité ainsi que les mesures à prendre pour maîtriser des situations de danger relatives aux structures. La modélisation des actions et les principes de vérification
COM-302: Principles of digital communications
This course is on the foundations of digital communication. The focus is on the transmission problem (rather than being on source coding).
Séances de cours associées (156)
Expressions régulières en Automata
Explore la conversion d'expressions régulières en automates pour une classification efficace des caractères.
Conception et synthèse FSM
Explique les étapes de la conception FSM, y compris la transition et la création de table de code.
Conception et synthèse FSM
Couvre la conception et la synthèse des machines à états finis, en mettant l'accent sur l'exhaustivité, la cohérence et les états fantômes.
MOOCs associés (9)
Algèbre Linéaire (Partie 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algèbre Linéaire (Partie 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algèbre Linéaire (Partie 2)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.