Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
Une machine à états finis (en anglais, FSM
pour finite state machine) ou automate à états finis (FSA pour finite state automata)
est une machine abstraite utilisée dans l'étude du calcul et des langues qui possède une quantité finie et constante de mémoire (les états). Une telle machine peut être
conceptualisée comme un graphe orienté. Il y a un nombre fini d'états, et chaque état a
des transitions vers zéro, un ou plusieurs états. Les états qui ne possèdent pas de transitions sont appelés états
finaux. La transition suivie est déterminée par la valeur donnée en entrée. Les machines à états finis sont étudiées dans la
théorie des automates, un sous-domaine de l'informatique théorique.
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.
| Sommaire |
Formellement, un automate fini déterministe (DFA) est un quintuplet: (S, Σ, T, s, A)
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.
Un automate fini non-déterministe (NFA) est un quintuplet: (S, Σ, T, s, A)
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, qui est le langage reconnu par le NFA.
Un automate fini non-déterministe généralisé (GNFA) est un quintuplet: (S, Σ, T, s, a)
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}.
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.
M = (S, Σ, T, s, A)
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.
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.)
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.
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.
Une machine à états finis peut être représentée en utilisant une table de transition d'état ou un diagramme d'état.
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.
