Automate fini
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
Un automate fini (on dit parfois machine à états finis), 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. 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. Un automate fini possède un nombre fini d'états distincts : il ne dispose donc que d'une mémoire bornée.
Un automate fini forme naturellement un graphe orienté étiqueté, dont les états sont les sommets et les transitions les arêtes étiquetées.
Sommaire |
[modifier] Utilisation
Il existe plusieurs types de machines à états finis :
Les accepteurs produisent en sortie une réponse « oui ou non », c'est-à-dire qu'ils acceptent ou rejettent l'entrée ; les systèmes de reconnaissance classent l'entrée par catégorie ; les capteurs sont employés pour produire un résultat en fonction de l'entrée donnée.
Les automates finis peuvent caractériser des langages de mots finis (le cas standard), des langages de mots infinis (automates de Rabin, automates de Büchi), ou encore divers types d'arbres (automates d'arbre), pour ne citer que les cas les plus importants.
Une autre distinction est faite entre les automates déterministes et non déterministes (qu'il conviendrait mieux de qualifier de « nondéterministe ») Les automates déterministes sont ceux où, pour chaque état, il y a au plus une transition pour chaque étiquette possible. Dans les automates non déterministes, il peut y avoir plus d'une transition à partir d'un état donné pour une étiquette donnée. Il est à noter que le terme de non déterministe n'est pas la négation de déterministe.
Les automates non déterministes sont habituellement utilisés en les convertissant au préalable en automates déterministes : dans le pire des cas, l'automate déterministe produit est exponentiellement plus grand que l'automate non déterministe (bien qu'il soit en général possible d'en diminuer considérablement le nombre d'états).
L'état standard d'acceptation pour les automates non déterministes exige qu'un certain calcul accepte l'entrée. Les automates alternatifs fournissent également une notion duale où, pour avoir acceptation, il faut que tous les calculs non déterministes possibles doivent être acceptés.
Indépendamment de la théorie, les machines à états finis se rencontrent également dans les circuits digitaux, où l'entrée, l'état et le résultat sont des vecteurs de bits de taille fixe (machines de Moore et machines de Mealy).
Dans les machines de Mealy, les actions (sorties) sont liées aux transitions, alors que dans les machines de Moore les actions sont liées aux états.
[modifier] Définitions formelles
[modifier] Automate fini déterministe
Formellement, un automate fini déterministe (DFA) est un quintuplet : M = (S,Σ,T,s,A)
- un ensemble d'états (S)
- un alphabet (Σ)
- une fonction de transition (
). - un état de départ (
) - un ensemble d'états acceptant (
)
La machine démarre dans l'état de départ et une séquence de symboles de son alphabet. Elle emploie la fonction de transition T pour déterminer le prochain état en utilisant l'état actuel et le symbole venant d'être lu. Si, à la fin de la lecture, elle est dans un état acceptant, on dit qu'elle accepte l'entrée, autrement on dit qu'elle la rejette. L'ensemble des entrées acceptées forme un langage, appelé langage reconnu par l'automate fini déterministe.
Un automate de Büchi déterministe opère sur des mots infinis. Un mot infini est accepté si l'automate de Büchi passe un nombre infini de fois par les états acceptants lorsqu'il passe sur ce mot.
[modifier] Automate fini non déterministe
Un automate fini non déterministe (NFA) est un quintuplet: M = (S,Σ,T,s,A)
- un ensemble d'états (S)
- un alphabet (Σ)
- une fonction de transition (
) - un état de départ ()
- un ensemble d'états acceptant ()
Où P(S) est l'ensemble des parties de S (aussi noté 2S) et 
est la séquence de taille nulle.
La machine M démarre dans l'état de départ et reçoit en entrée une séquence w de symboles de son alphabet. Elle emploie la relation de transition T pour déterminer le ou les prochains états atteignables en utilisant les états actuellement atteignables et le symbole venant d'être lu. On dit que l'automate non-déterministe M accepte l'entrée w si un des états acceptants est atteignable au terme de la lecture de l'entrée. Sinon, M rejette w. L'ensemble des entrées acceptées forme un langage dénoté généralement par L(M).
[modifier] Automate fini non déterministe généralisé
Un automate fini non déterministe généralisé (GNFA) est un quintuplet: (S,Σ,T,s,a)
- S est un ensemble fini d'états
- Σ est un ensemble fini de symboles
- est l'état de départ
est l'état d'acceptation
Où R est la collection de toutes les expressions rationnelles sur l'alphabet Σ.
Un DFA ou un NFA peut facilement être converti en GNFA et alors le GNFA peut être facilement converti en expression rationnelle en réduisant le nombre d'états jusque à ce que S = {s,a}.
[modifier] Exemples de machines à états finis
[modifier] Machine à états finis déterministe
L'exemple suivant explique une machine à états finis déterministe sur un alphabet binaire, qui détermine si l'entrée contient un nombre pair de 0.
M = (S,Σ,T,s,A)
- S = {S1,S2}
- Σ = {0,1}
- s = S1
- A = {S1}
- La fonction de transition T est visualisée par le graphe dirigé montré du côté droit et est définie comme suit :
- T(S1,0) = S2
- T(S1,1) = S1
- T(S2,0) = S1
- T(S2,1) = S2
L'état S1 représente qu'il y a eu un nombre pair de 0 dans l'entrée jusqu'à présent, alors que S2 signifie un nombre impair. Un 1 dans l'entrée ne change pas l'état de l'automate. Quand l'entrée finit, l'état montrera si l'entrée a contenu un nombre pair de 0 ou pas.
[modifier] Langages formels et lien avec les expressions rationnelles
Les langages reconnus par les automates finis (déterministes ou non) sont exactement les langages qui peuvent être décrits par les expressions rationnelles. (Ce résultat s'appelle le théorème de Kleene.)
[modifier] Optimisation et mise sous forme canonique
Le problème de l'optimisation, ou minimisation, d'une machine à états finis, c'est-à-dire de trouver la machine avec le plus petit nombre d'états et qui exécute la même fonction, est un problème décidable ; à la différence de problèmes similaires pour des machines informatiques plus puissantes. En outre, il est possible de construire une version canonique de n'importe quel FSM, afin de déterminer l'égalité. Ces deux problèmes peuvent être résolus en utilisant un algorithme de coloriage.
[modifier] Puissance informatique
Les machines à états finis peuvent uniquement identifier des langages rationnels, et par conséquent elles sont moins puissantes que les machines de Turing - il y a des problèmes que l'on peut décider mais qui ne sont pas calculables en utilisant une machine à états finis.
Pour chaque machine non déterministe ayant n états, une machine déterministe de puissance égale peut être construite avec un algorithme. Cette machine déterministe a cependant au pire cas un nombre d'états égal au nombre de parties de l'ensemble des états de la machine initiale, c'est à dire 2n
[modifier] Représentation
Une machine à états finis peut être représentée en utilisant une table de transition d'état ou un diagramme d'état.
[modifier] Exécution
Une machine à états finis peut être implémentée sous forme logicielle avec une matrice de transition d'état. Dans certains cas, il est plus avantageux d'utiliser une matrice clairsemée implémentée avec des listes liées ou un énorme switch pour détecter l'état interne et puis les différents switch plus petits pour décoder le symbole d'entrée.
Une machine à états finis peut aussi être implémentée sous forme matérielle avec un dispositif de logique programmable.
