Ê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 non déterministe
Résumé
Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte.
On distingue les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automaton ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il est indifférent qu'il soit déterministe ou non.
Les automates finis (déterministes ou non) reconnaissent exactement des langages rationnels. Ce sont les machines les plus simples dans la hiérarchie de Chomsky, et par conséquent ils sont moins puissants que les automates à pile et, bien entendu, que les machines de Turing.
Un automate est constitué d'états et de transitions. Son comportement est dirigé par un mot fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. Dans l'exemple ci-dessus, pour l'entrée , et si l'automate démarre en , il passe successivement par les états , le calcul correspondant est :
L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. On peut très bien considérer des automates sans limitation sur le nombre d'états : la théorie qui en résulte est très analogue à la théorie habituelle.
Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées.
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.
Concepts associés (25)
Théorie des automates
En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.
Transducteur fini
En informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie.
Automate fini alternant
En informatique théorique, et notamment en théorie des automates, un automate fini alternant est une extension des automates finis. Dans un automate fini non déterministe usuel, un mot est accepté si, parmi les états atteints, il y a au moins un état final. Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation.
Cours associés (14)
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
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).
CS-251: Theory of computation
This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica
Séances de cours associées (142)
Ondes à deux flots
Explore les ondes à deux fluides en physique du plasma, en discutant des relations de dispersion et des caractéristiques de propagation des vagues.
Des expressions régulières aux automatismes
Explore la transition des expressions régulières aux automates finis, couvrant la création de lexers, les différents types d'automates et les processus de conversion.
Correction d'erreur d'orthographe
Explore la correction d'erreurs orthographiques, y compris les néologismes et les emprunts, en utilisant la distance d'édition et les automates à états finis.
MOOCs associés (14)
Plasma Physics: Introduction
Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.
Plasma Physics: Introduction
Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.
Plasma Physics: Applications
Learn about plasma applications from nuclear fusion powering the sun, to making integrated circuits, to generating electricity.