Machine abstraite définie par un quintuplet
(Q, ∑, T, s, A), avec :
L’ensemble des états acceptés forme le langage reconnu par l’automate à états finis.
Soit M=(S, ∑, T, s, A), avec
T | 0 | 1 | |
---|---|---|---|
q0 | q1 | q0 | transi- |
q1 | q0 | q1 | tions |
état | signaux |
Les états représentent la mémoire de la machine. Problème : une fois la machine définie, on ne peut plus ajouter, modifier ou supprimer des états. Ceci limite beaucoup la puissance de la machine.
Les langages reconnus par les automates finis sont exactement les langages pouvant être décrits par les expressions régulières.
Les FSM sont beaucoup utilisés en informatique (réseaux, …)