Outils pour utilisateurs

Outils du site


glossaire:fsm

Table des matières

FSM

Finite State Machines

Un automate fini (on dit parfois machine à états finie), en anglais finite state automaton ou finite state machine (FSA, FSM), est une machine abstraite utilisée en théorie de la calculabilité et dans l'étude des langages formels. C'est un outil fondamental en Informatique, où il intervient notamment en compilation des langages informatiques (procédé permettant de passer d'un langage de haut niveau en langage machine binaire).

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. L'automate est dit « fini » car il possède un nombre fini d'états distincts : il ne dispose donc que d'une mémoire bornée.

Un automate fini forme un graphe orienté étiqueté, dont les états sont les sommets et les transitions les arêtes étiquetées.

glossaire/fsm.txt · Dernière modification: 19/05/2012 00:18 (modification externe)