Automate fini
Un automate fini forme naturellement un graphe orienté, dont les états sont les sommets et les transitions les arêtes.
| Sommaire |
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. 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. 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.
Définitions formelles
Automate fini déterministe
Formellement, un automate fini déterministe (DFA) est un quintuplet: (S, Σ, T, s, A)
- un alphabet (Σ)
- un ensemble d'états (S)
- une fonction de transition (T : S × Σ → S).
- un état de départ (s ∈ S)
- un ensemble d'états acceptant (A ⊆ S)
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, quand il a fini 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, qui est le langage reconnu par le DFA.
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.
Automate fini non déterministe
Un automate fini non déterministe (NFA) est un quintuplet: (S, Σ, T, s, A)
- un alphabet (Σ)
- un ensemble d'états (S)
- une fonction de transition (T : S × (Σ ∪{ε}) → P(S)).
- un état de départ (s ∈ S)
- un ensemble d'états acceptant (A ⊆ S)
Où P(S) est l'ensemble des parties de S et de ε est la séquence de taille nulle.
La machine démarre dans l'état de départ et une séquence de symboles de son alphabet. Elle emploie la relation de transition T pour déterminer le ou les prochains états en utilisant l'état actuel et le symbole venant d'être lu ou la séquence vide. Si, quand il a fini 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.
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
- T : (S -{a}) × (S - {s}) → R
- s ∈ S est l'état de départ
- a ∈ S est l'état d'acceptation
Où R est la collection de toutes les expressions régulières sur l'alphabet Σ.
Un DFA ou un NFA peut facilement être converti en GNFA et alors le GNFA peut être facilement converti en expression régulière en réduisant le nombre d'états jusque à ce que S = {s, a}.
Exemples de machines à états finis
Machine à états finis déterministe
L'exemple suivant explique une machine à états finis déterministe (m) sur un alphabet binaire, qui détermine si l'entrée contient un nombre pair de 0.
FSM.png
Image:FSM.png
M = (S, Σ, T, s, A)
- Σ = {0, 1}
- S = {S1, S2}
- s = S1
- A = {S1}
- La fonction de transition T est visualisée par le graphe dirigé montré du côté droit et est défini 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.
Langages formels et lien avec les expressions régulières
Les langages reconnus par les automates finis (déterministes ou non) sont exactement les langages qui peuvent être décrits par les expressions régulières. (Ce résultat s'appelle le théorème de Kleene.)
Optimisation et Canonicalisation
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.
Puissance informatique
Les machines à états finis peuvent uniquement identifier des langages réguliers, 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, une machine déterministe de puissance égale peut être construite avec un algorithme.
Représentation
Une machine à états finis peut être représentée en utilisant une table de transition d'état ou un diagramme d'état.
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.