===== Automate (ou machine) à états finis =====

Machine abstraite définie par un quintuplet 
	(Q, ∑, T, s, A), avec :

  * Q, ensemble fini d’états,
  * <jsm>\Sigma</jsm>, alphabet fini,
  * T, fonction de transition (<jsm>T: Q\times \Sigma\rightarrow Q</jsm>)‏
  * q<sub>d</sub>, état de départ ∈ Q
  * A, ensemble d’états « acceptants » ∈ Q

L’ensemble des états acceptés forme le langage reconnu par l’automate à états finis.

==== Exemple de FSM (finite state machine) ====
‏
Soit M=(S, ∑, T, s, A), avec
  * ∑ = {0,1}
  * Q={q0,q1},
  * q<sub>d</sub>=q<sub>0</sub>,
  * A=q0.

^ T             ^  0             ^   1           ^  ^
^ q<sub>0</sub> |  q<sub>1</sub>  |  q<sub>0</sub>  | transi- |
^ q<sub>1</sub> |  q<sub>0</sub>  |  q<sub>1</sub>  | tions |
^  état ^   signaux  ^^  ^
==== Langages reconnus par les FSM ====

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. 

=== Théorème de Kleene : ===

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, …)‏