Automate (ou machine) à états finis

Machine abstraite définie par un quintuplet

(Q, ∑, T, s, A), avec :
  • Q, ensemble fini d’états,
  • \Sigma, alphabet fini,
  • T, fonction de transition (T: Q\times \Sigma\rightarrow Q)‏
  • qd, é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},
  • qd=q0,
  • A=q0.
T 0 1
q0 q1 q0 transi-
q1 q0 q1 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, …)‏

 
m1ilc/search_fsm.txt · Dernière modification: 2010/05/20 11:26 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki