Machine à états finis - Finite-state machine
Une machine à états finis ( FSM ) ou un automate à états finis ( FSA , pluriel : automates ), un automate fini , ou simplement une machine à états , est un modèle mathématique de calcul . C'est une machine abstraite qui peut être dans exactement l'un d'un nombre fini d' états à un moment donné. Le FSM peut passer d'un état à un autre en réponse à certaines entrées ; le passage d'un état à un autre s'appelle une transition . Un FSM est défini par une liste de ses états, son état initial et les entrées qui déclenchent chaque transition. Machines à états finis sont de deux types- machines déterministes à états finis et des machines à l' état de non-déterministe fini . Une machine à états finis déterministe peut être construite équivalente à n'importe quelle machine non déterministe.
Le comportement des machines à états peut être observé dans de nombreux appareils de la société moderne qui effectuent une séquence prédéterminée d'actions en fonction d'une séquence d'événements avec lesquels ils sont présentés. Des exemples simples sont les distributeurs automatiques , qui distribuent des produits lorsque la combinaison appropriée de pièces est déposée, les ascenseurs , dont la séquence d'arrêts est déterminée par les étages demandés par les passagers, les feux de circulation , qui changent de séquence lorsque les voitures attendent, et les serrures à combinaison , qui nécessitent l'entrée d'une séquence de nombres dans le bon ordre.
La machine à états finis a moins de puissance de calcul que certains autres modèles de calcul tels que la machine de Turing . La distinction de puissance de calcul signifie qu'il y a des tâches de calcul qu'une machine de Turing peut faire mais pas un FSM. En effet, la mémoire d' un FSM est limitée par le nombre d'états dont il dispose. Une machine à états finis a la même puissance de calcul qu'une machine de Turing qui est restreinte de telle sorte que sa tête ne peut effectuer que des opérations de « lecture », et doit toujours se déplacer de gauche à droite. Les FSM sont étudiées dans le domaine plus général de la théorie des automates .
Exemple : tourniquet à pièces
Un exemple de mécanisme simple qui peut être modélisé par une machine d'état est un tourniquet . Un tourniquet, utilisé pour contrôler l'accès aux métros et aux manèges des parcs d'attractions, est une porte avec trois bras rotatifs à hauteur de taille, un à travers l'entrée. Initialement, les bras sont verrouillés, bloquant l'entrée, empêchant les clients de passer. Le dépôt d'une pièce ou d'un jeton dans une fente sur le tourniquet déverrouille les bras, permettant à un seul client de passer. Après le passage du client, les bras sont à nouveau verrouillés jusqu'à ce qu'une autre pièce soit insérée.
Considéré comme une machine à états, le tourniquet a deux états possibles : Verrouillé et Déverrouillé . Il y a deux entrées possibles qui affectent son état : mettre une pièce dans la fente ( pièce ) et pousser le bras ( pousser ). A l'état verrouillé, la poussée sur le bras n'a aucun effet ; quel que soit le nombre de fois où la poussée d' entrée est donnée, il reste dans l'état verrouillé. Mettre une pièce de monnaie, c'est-à-dire donner à la machine une entrée de pièce de monnaie , fait passer l'état de Verrouillé à Déverrouillé . Dans l'état déverrouillé, mettre des pièces supplémentaires n'a aucun effet ; c'est-à-dire que donner des entrées de pièces supplémentaires ne change pas l'état. Cependant, un client poussant à travers les bras, donnant une entrée de poussée , remet l'état à Verrouillé .
La machine d'état du tourniquet peut être représentée par une table état-transition , montrant pour chaque état possible, les transitions entre eux (en fonction des entrées données à la machine) et les sorties résultant de chaque entrée :
État actuel Saisir État suivant Sortir Fermé à clé pièce de monnaie Débloqué Déverrouille le tourniquet pour que le client puisse passer. pousser Fermé à clé Rien Débloqué pièce de monnaie Débloqué Rien pousser Fermé à clé Lorsque le client a poussé, verrouille le tourniquet.
La machine d'état du tourniquet peut également être représentée par un graphe orienté appelé diagramme d'état (ci-dessus) . Chaque état est représenté par un nœud ( cercle ). Les bords ( flèches ) montrent les transitions d'un état à un autre. Chaque flèche est étiquetée avec l'entrée qui déclenche cette transition. Une entrée qui ne provoque pas de changement d'état (comme une entrée de pièce dans l' état Déverrouillé ) est représentée par une flèche circulaire revenant à l'état d'origine. La flèche dans le nœud verrouillé à partir du point noir indique qu'il s'agit de l'état initial.
Concepts et terminologie
Un état est une description de l'état d'un système qui attend d'exécuter une transition . Une transition est un ensemble d'actions à exécuter lorsqu'une condition est remplie ou lorsqu'un événement est reçu. Par exemple, lors de l'utilisation d'un système audio pour écouter la radio (le système est dans l'état « radio »), la réception d'un stimulus « suivant » entraîne le passage à la station suivante. Lorsque le système est dans l'état « CD », le stimulus « suivant » entraîne le passage à la piste suivante. Des stimuli identiques déclenchent des actions différentes selon l'état actuel.
Dans certaines représentations de machines à états finis, il est également possible d'associer des actions à un état :
- une action de saisie : effectuée lors de la saisie de l'état, et
- une action de sortie : effectuée lors de la sortie de l'état.
Représentations
Tableau d'état/d'événement
Plusieurs types de tables de transition d'état sont utilisés. La représentation la plus courante est illustrée ci-dessous : la combinaison de l'état actuel (par exemple B) et de l'entrée (par exemple Y) montre l'état suivant (par exemple C). Les informations complètes de l'action ne sont pas directement décrites dans le tableau et ne peuvent être ajoutées qu'à l'aide de notes de bas de page. Une définition FSM incluant les informations complètes de l'action est possible à l'aide de tables d'état (voir aussi machine virtuelle à états finis ).
État actuel Saisir
|
État A | État B | État C |
---|---|---|---|
Entrée X | ... | ... | ... |
Saisie O | ... | État C | ... |
Saisie Z | ... | ... | ... |
Machines d'état UML
Le langage de modélisation unifié a une notation pour décrire les machines à états. Les machines à états UML surmontent les limitations des machines à états finis traditionnelles tout en conservant leurs principaux avantages. Les machines à états UML introduisent les nouveaux concepts d' états hiérarchiquement imbriqués et de régions orthogonales , tout en étendant la notion d' actions . Les machines à états UML ont les caractéristiques à la fois des machines de Mealy et des machines de Moore . Ils prennent en charge des actions qui dépendent à la fois de l'état du système et de l' événement déclencheur , comme dans les machines Mealy, ainsi que des actions d'entrée et de sortie , qui sont associées à des états plutôt qu'à des transitions, comme dans les machines Moore.
Machines d'état SDL
Le langage de spécification et de description est une norme de l' UIT qui inclut des symboles graphiques pour décrire les actions de la transition :
- envoyer un événement
- recevoir un événement
- démarrer une minuterie
- annuler une minuterie
- démarrer une autre machine à états simultanés
- décision
SDL intègre des types de données de base appelés « types de données abstraits », un langage d'action et une sémantique d'exécution afin de rendre la machine à états finis exécutable.
Autres diagrammes d'état
Il existe un grand nombre de variantes pour représenter un FSM tel que celui de la figure 3.
Usage
En plus de leur utilisation dans la modélisation des systèmes réactifs présentés ici, les machines à états finis sont importantes dans de nombreux domaines différents, notamment le génie électrique , la linguistique , l' informatique , la philosophie , la biologie , les mathématiques , la programmation de jeux vidéo et la logique . Les machines à états finis sont une classe d'automates étudiée en théorie des automates et en théorie du calcul . En informatique, les machines à états finis sont largement utilisées dans la modélisation du comportement des applications, la conception de systèmes numériques matériels , le génie logiciel , les compilateurs , les protocoles réseau et l'étude du calcul et des langages.
Classification
Les machines à états finis peuvent être subdivisées en accepteurs, classificateurs, transducteurs et séquenceurs.
Accepteurs
Les accepteurs (également appelés détecteurs ou reconnaisseurs ) produisent une sortie binaire, indiquant si l'entrée reçue est acceptée ou non. Chaque état d'un accepteur est soit acceptant, soit non acceptant . Une fois que toutes les entrées ont été reçues, si l'état actuel est un état d'acceptation, l'entrée est acceptée ; sinon il est rejeté. En règle générale, l'entrée est une séquence de symboles (caractères); les actions ne sont pas utilisées. L'état de départ peut également être un état d'acceptation, auquel cas l'accepteur accepte la chaîne vide. L'exemple de la figure 4 montre un accepteur qui accepte la chaîne "nice". Dans cet accepteur, le seul état d'acceptation est l'état 7.
Un ensemble (éventuellement infini) de séquences de symboles, appelé langage formel , est un langage régulier s'il existe un accepteur qui accepte exactement cet ensemble. Par exemple, l'ensemble des chaînes binaires avec un nombre pair de zéros est un langage régulier (cf. Fig. 5), alors que l'ensemble de toutes les chaînes dont la longueur est un nombre premier ne l'est pas.
Un accepteur pourrait également être décrit comme définissant un langage qui contiendrait chaque chaîne acceptée par l'accepteur mais aucune de celles rejetées ; cette langue est acceptée par l'accepteur. Par définition, les langages acceptés par les accepteurs sont les langages réguliers .
Le problème de la détermination du langage accepté par un accepteur donné est une instance du problème du chemin algébrique — lui- même une généralisation du problème du plus court chemin aux graphes dont les arêtes sont pondérées par les éléments d'un semi-anneau (arbitraire) .
Un exemple d'état d'acceptation apparaît sur la figure 5 : un automate fini déterministe (DFA) qui détecte si la chaîne d'entrée binaire contient un nombre pair de 0.
S 1 (qui est également l'état de départ) indique l'état auquel un nombre pair de 0 a été entré. S 1 est donc un état acceptant. Cet accepteur finira dans un état d'acceptation, si la chaîne binaire contient un nombre pair de 0 (y compris toute chaîne binaire ne contenant pas de 0). Des exemples de chaînes acceptées par cet accepteur sont ε (la chaîne vide ), 1, 11, 11..., 00, 010, 1010, 10110, etc.
Classificateurs
Les classificateurs sont une généralisation des accepteurs qui produisent une sortie n -aire où n est strictement supérieur à deux.
Transducteurs
Les transducteurs produisent une sortie basée sur une entrée donnée et/ou un état à l'aide d'actions. Ils sont utilisés pour des applications de contrôle et dans le domaine de la linguistique informatique .
Dans les applications de contrôle, on distingue deux types :
- Machine de Moore
- Le FSM utilise uniquement des actions d'entrée, c'est-à-dire que la sortie ne dépend que de l'état. L'avantage du modèle de Moore est une simplification du comportement. Considérez une porte d'ascenseur. La machine d'état reconnaît deux commandes : "command_open" et "command_close", qui déclenchent des changements d'état. L'action d'entrée (E:) à l'état "Ouverture" démarre un moteur d'ouverture de la porte, l'action d'entrée à l'état "Fermeture" démarre un moteur dans l'autre sens fermant la porte. Les états "Ouvert" et "Fermé" arrêtent le moteur lorsqu'il est complètement ouvert ou fermé. Ils signalent au monde extérieur (par exemple, à d'autres machines d'état) la situation : « la porte est ouverte » ou « la porte est fermée ».
- Machine à farine
- Le FSM utilise également des actions d'entrée, c'est-à-dire que la sortie dépend de l'entrée et de l'état. L'utilisation d'un FSM Mealy conduit souvent à une réduction du nombre d'états. L'exemple de la figure 7 montre un FSM Mealy implémentant le même comportement que dans l'exemple de Moore (le comportement dépend du modèle d'exécution FSM implémenté et fonctionnera, par exemple, pour le FSM virtuel mais pas pour le FSM événementiel ). Il y a deux actions d'entrée (I :) : "démarrer le moteur pour fermer la porte si command_close arrive" et "démarrer le moteur dans l'autre sens pour ouvrir la porte si command_open arrive". Les états intermédiaires "ouverture" et "fermeture" ne sont pas représentés.
Séquenceurs
Les séquenceurs (également appelés générateurs ) sont une sous-classe d'accepteurs et de transducteurs qui ont un alphabet d'entrée à une seule lettre. Ils produisent une seule séquence qui peut être considérée comme une séquence de sortie de sorties d'accepteur ou de transducteur.
Déterminisme
Une autre distinction est faite entre les automates déterministes ( DFA ) et non déterministes ( NFA , GNFA ). Dans un automate déterministe, chaque état a exactement une transition pour chaque entrée possible. Dans un automate non déterministe, une entrée peut conduire à une, plusieurs ou aucune transition pour un état donné. L' algorithme de construction de powerset peut transformer n'importe quel automate non déterministe en un automate déterministe (généralement plus complexe) avec des fonctionnalités identiques.
Une machine à états finis avec un seul état est appelée « FSM combinatoire ». Il n'autorise les actions que lors de la transition vers un état. Ce concept est utile dans les cas où un certain nombre de machines à états finis sont nécessaires pour travailler ensemble, et lorsqu'il est commode de considérer une partie purement combinatoire comme une forme de FSM pour s'adapter aux outils de conception.
Sémantique alternative
Il existe d'autres ensembles de sémantiques disponibles pour représenter les machines à états. Par exemple, il existe des outils de modélisation et de conception de logique pour les contrôleurs embarqués. Ils combinent des machines à états hiérarchiques (qui ont généralement plus d'un état actuel), des graphes de flux et des tables de vérité dans un seul langage, ce qui entraîne un formalisme et un ensemble de sémantiques différents. Ces graphiques, comme les machines à états d'origine de Harel, prennent en charge les états imbriqués hiérarchiquement, les régions orthogonales , les actions d'état et les actions de transition.
Modèle mathématique
Conformément à la classification générale, on trouve les définitions formelles suivantes.
Une machine à états finis déterministe ou un accepteur à états finis déterministe est un quintuple , où :
- est l' alphabet d' entrée (un ensemble fini non vide de symboles) ;
- est un ensemble fini non vide d'états ;
- est un état initial, un élément de ;
- est la fonction de transition d'état : (dans un automate fini non déterministe ce serait , c'est -à- dire renverrait un ensemble d'états) ;
- est l'ensemble des états finaux, un sous-ensemble (éventuellement vide) de .
Pour les FSM déterministes et non déterministes, il est conventionnel de laisser être une fonction partielle , c'est -à- dire qu'il n'est pas nécessaire de définir pour chaque combinaison de et . Si un FSM est dans un état , le symbole suivant est et n'est pas défini, alors peut annoncer une erreur (c'est-à-dire rejeter l'entrée). Ceci est utile dans les définitions des machines à états généraux, mais moins utile lors de la transformation de la machine. Certains algorithmes dans leur forme par défaut peuvent nécessiter des fonctions totales.
Une machine à états finis a la même puissance de calcul qu'une machine de Turing qui est restreinte de telle sorte que sa tête ne peut effectuer que des opérations de « lecture », et doit toujours se déplacer de gauche à droite. C'est-à-dire que chaque langage formel accepté par une machine à états finis est accepté par un tel type de machine de Turing restreinte, et vice versa.
Un transducteur à états finis est un sextuple , où :
- est l' alphabet d' entrée (un ensemble fini non vide de symboles) ;
- est l'alphabet de sortie (un ensemble fini non vide de symboles) ;
- est un ensemble fini non vide d'états ;
- est l'état initial, un élément de ;
- est la fonction d'état-transition : ;
- est la fonction de sortie.
Si la fonction de sortie dépend de l'état et du symbole d'entrée ( ) cette définition correspond au modèle de Mealy et peut être modélisée comme une machine de Mealy . Si la fonction de sortie ne dépend que de l'état ( ), cette définition correspond au modèle de Moore et peut être modélisée comme une machine de Moore . Une machine à états finis sans aucune fonction de sortie est appelée semi -automate ou système de transition .
Si nous ne tenons pas compte du premier symbole de sortie d'une machine de Moore, , alors il peut être facilement converti en une machine de Mealy équivalente en sortie en définissant la fonction de sortie de chaque transition de Mealy (c'est-à-dire en étiquetant chaque arête) avec le symbole de sortie donné de la destination Moore Etat. La transformation inverse est moins simple car un état de machine Mealy peut avoir différentes étiquettes de sortie sur ses transitions entrantes (bords). Chaque état de ce type doit être divisé en plusieurs états de machine de Moore, un pour chaque symbole de sortie incident.
Optimisation
Optimiser un FSM, c'est trouver une machine avec le nombre minimum d'états qui exécute la même fonction. L'algorithme connu le plus rapide pour ce faire est l' algorithme de minimisation de Hopcroft . D'autres techniques incluent l'utilisation d'une table d'implication ou la procédure de réduction de Moore. De plus, les FSA acycliques peuvent être minimisées en temps linéaire.
Mise en œuvre
Applications matérielles
Dans un circuit numérique , un FSM peut être construit à l'aide d'un dispositif logique programmable , d'un contrôleur logique programmable , de portes logiques et de bascules ou de relais . Plus précisément, une mise en œuvre matérielle nécessite un registre pour stocker les variables d'état, un bloc de logique combinatoire qui détermine la transition d'état et un deuxième bloc de logique combinatoire qui détermine la sortie d'un FSM. L'une des implémentations matérielles classiques est le contrôleur Richards .
Dans une machine Medvedev , la sortie est directement connectée aux bascules d'état minimisant le délai entre les bascules et la sortie.
Le codage par état pour les machines d'état à faible puissance peut être optimisé pour minimiser la consommation d'énergie.
Applications de programme
Les concepts suivants sont couramment utilisés pour créer des applications logicielles avec des machines à états finis :
- Programmation basée sur des automates
- Machine à états finis pilotée par événement
- Machine virtuelle à états finis
- Modèle de conception d'état
Machines à états finis et compilateurs
Les automates finis sont souvent utilisés dans le frontend des compilateurs de langage de programmation. Une telle interface peut comprendre plusieurs machines à états finis qui implémentent un analyseur lexical et un parseur. À partir d'une séquence de caractères, l'analyseur lexical construit une séquence de jetons de langage (tels que des mots réservés, des littéraux et des identifiants) à partir desquels l'analyseur syntaxique construit un arbre syntaxique. L'analyseur lexical et l'analyseur syntaxique gèrent les parties régulières et hors contexte de la grammaire du langage de programmation.
Voir également
- Machines à états abstraits (ASM)
- Intelligence artificielle (IA)
- Langage machine à états abstraits (AsmL)
- Modèle de comportement
- Machine à états finis communicante
- Système de contrôle
- Tableau de contrôle
- Tables de décision
- DEVS : Spécification du système d'événements discrets
- Machine à états finis étendue (EFSM)
- Machine à états finis avec chemin de données
- Gézel
- Modèle de Markov caché
- Séquence de référencement
- Synthèse FSM basse consommation
- filet de Pétri
- Automate de poussée
- Automates quantiques finis (QFA)
- Langue reconnaissable
- SCXML
- Semi-automate
- Action en semi-groupe
- Logique séquentielle
- Langage de spécification et de description
- Diagramme d'état
- Modèle d'état
- Séquence de synchronisation
- Monoïde de transformation
- Monoïde de transition
- Système de transition
- Arbre automate
- Machine de Turing
- Machine d'état UML
- Séquence d'entrée/sortie unique (UIO)
Les références
Lectures complémentaires
Général
- Sakarovitch, Jacques (2009). Éléments de théorie des automates . Traduit du français par Ruben Thomas. Presse de l'Université de Cambridge . ISBN 978-0-521-84425-3. Zbl 1188.68177 .
- Wagner, F., "Logiciel de modélisation avec des machines à états finis: une approche pratique", Publications Auerbach, 2006, ISBN 0-8493-8086-3 .
- UIT-T, Recommandation Z.100 Langage de spécification et de description (SDL)
- Samek, M., Diagrammes d'états pratiques en C/C++ , CMP Books, 2002, ISBN 1-57820-110-1 .
- Samek, M., Tableaux d'états pratiques UML en C/C++, 2e édition , Newnes, 2008, ISBN 0-7506-8706-1 .
- Gardner, T., Gestion avancée de l'État , 2007
- Cassandras, C., Lafortune, S., "Introduction aux systèmes à événements discrets". Kluwer, 1999, ISBN 0-7923-8609-4 .
- Timothy Kam, Synthèse des machines à états finis : optimisation fonctionnelle . Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
- Tiziano Villa, Synthèse des machines à états finis : optimisation logique . Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
- Carroll, J., Long, D., Théorie des automates finis avec une introduction aux langages formels . Prentice Hall, falaises d'Englewood, 1989.
- Kohavi, Z., Théorie de la commutation et des automates finis . McGraw-Hill, 1978.
- Gill, A., Introduction à la théorie des machines à états finis . McGraw-Hill, 1962.
- Ginsburg, S., Une introduction à la théorie mathématique des machines . Addison-Wesley, 1962.
Machines à états finis (théorie des automates) en informatique théorique
- Arbib, Michael A. (1969). Théories des automates abstraits (1ère éd.). Englewood Cliffs, NJ : Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
- Bobrow, Leonard S.; Arbib, Michael A. (1974). Mathématiques discrètes : algèbre appliquée pour l'informatique et les sciences de l'information (1ère éd.). Philadelphie : WB Saunders Company, Inc. ISBN 978-0-7216-1768-8.
- Booth, Taylor L. (1967). Machines séquentielles et théorie des automates (1ère éd.). New York : John Wiley and Sons, Inc. Numéro de catalogue 67-25924 de la carte de la Bibliothèque du Congrès.
- Boolos, Georges; Jeffrey, Richard (1999) [1989]. Calculabilité et logique (3e éd.). Cambridge, Angleterre : Cambridge University Press. ISBN 978-0-521-20402-6.
- Brookshear, J. Glenn (1989). Théorie du calcul : langages formels, automates et complexité . Redwood City, Californie : Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
- Davis, Martin ; Sigal, Ron ; Weyuker, Elaine J. (1994). Calculabilité, complexité et langages et logique : principes fondamentaux de l'informatique théorique (2e éd.). San Diego : Academic Press, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
- Hopcroft, John; Ullman, Jeffrey (1979). Introduction à la théorie, aux langages et au calcul des automates (1ère éd.). Messe de lecture : Addison-Wesley. ISBN 978-0-201-02988-8.
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction à la théorie des automates, aux langages et au calcul (2e éd.). Messe de lecture : Addison-Wesley. ISBN 978-0-201-44124-6.
- Hopkin, David ; Moss, Barbara (1976). Automates . New York : Elsevier Nord-Hollande. ISBN 978-0-444-00249-5.
- Kozen, Dexter C. (1997). Automates et calculabilité (1ère éd.). New York : Springer-Verlag. ISBN 978-0-387-94907-9.
- Lewis, Harry R. ; Papadimitriou, Christos H. (1998). Éléments de la théorie du calcul (2e éd.). Upper Saddle River, New Jersey : Prentice-Hall. ISBN 978-0-13-262478-7.
- Linz, Pierre (2006). Langages formels et automates (4e éd.). Sudbury, MA : Jones et Bartlett. ISBN 978-0-7637-3798-6.
- Minsky, Marvin (1967). Calcul: Machines finies et infinies (1ère éd.). New Jersey : Prentice-Hall.
- Papadimitriou, Christos (1993). Complexité computationnelle (1ère éd.). Addison Wesley. ISBN 978-0-201-53082-7.
- Pipenger, Nicolas (1997). Théories de calculabilité (1ère éd.). Cambridge, Angleterre : Cambridge University Press. ISBN 978-0-521-55380-3.
- Rodger, Suzanne ; Finley, Thomas (2006). JFLAP : un package interactif de langages formels et d'automates (1ère éd.). Sudbury, MA : Jones et Bartlett. ISBN 978-0-7637-3834-1.
- Sipser, Michael (2006). Introduction à la théorie du calcul (2e éd.). Boston Mass : Technologie du cours Thomson. ISBN 978-0-534-95097-2.
- Bois, Derick (1987). Théorie du calcul (1ère éd.). New York : Harper & Row, Publishers, Inc. ISBN 978-0-06-047208-5.
Machines à états abstraits en informatique théorique
- Gurevich, Yuri (juillet 2000). "Les machines à états abstraits séquentiels capturent des algorithmes séquentiels" (PDF) . Transactions ACM sur la logique informatique . 1 (1) : 77-111. CiteSeerX 10.1.1.146.3017 . doi : 10.1145/343369.343384 . S2CID 2031696 .
Apprentissage automatique à l'aide d'algorithmes à états finis
- Mitchell, Tom M. (1997). Apprentissage automatique (1ère éd.). New York : WCB/McGraw-Hill Corporation. ISBN 978-0-07-042807-2.
Ingénierie matérielle : minimisation d'état et synthèse de circuits séquentiels
- Booth, Taylor L. (1967). Machines séquentielles et théorie des automates (1ère éd.). New York : John Wiley and Sons, Inc. Numéro de catalogue 67-25924 de la carte de la Bibliothèque du Congrès.
- Booth, Taylor L. (1971). Réseaux numériques et systèmes informatiques (1ère éd.). New York : John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
- McCluskey, EJ (1965). Introduction à la théorie des circuits de commutation (1ère éd.). New York : McGraw-Hill Book Company, Inc. Numéro de catalogue 65-17394 de la carte de la Bibliothèque du Congrès.
- Hill, Fredrick J.; Peterson, Gerald R. (1965). Introduction à la théorie des circuits de commutation (1ère éd.). New York : McGraw-Hill Book Company. Library of Congress Card Numéro de catalogue 65-17394.
Processus de chaîne de Markov finis
- « On peut penser à une chaîne de Markov en tant que processus qui se déplace successivement à travers un ensemble d'états s 1 , s 2 , ..., s r . ... si elle est en état s i on passe à l'étape suivante à l' état de la j avec probabilité p ij . Ces probabilités peuvent être présentées sous la forme d'une matrice de transition" (Kemeny (1959), p. 384)
Les processus de chaîne de Markov finis sont également connus sous le nom de sous- décalages de type fini .
- Booth, Taylor L. (1967). Machines séquentielles et théorie des automates (1ère éd.). New York : John Wiley and Sons, Inc. Numéro de catalogue 67-25924 de la carte de la Bibliothèque du Congrès.
- Kemeny, John G.; Mirkil, Hazleton ; Snell, J. Laurie; Thompson, Gerald L. (1959). Structures mathématiques finies (1ère éd.). Englewood Cliffs, NJ : Prentice-Hall, Inc. Library of Congress Card Numéro de catalogue 59-12841. Chapitre 6 "Chaînes de Markov finies".
Liens externes
- Automates à états finis à Curlie
- Modélisation d'un comportement d'IA simple à l'aide d'une machine à états finis Exemple d'utilisation dans les jeux vidéo
- Dictionnaire gratuit en ligne de la description informatique des machines à états finis
- Dictionnaire NIST des algorithmes et des structures de données description des machines à états finis
- Un bref aperçu des types de machines à états , comparant les aspects théoriques des machines à états Mealy, Moore, Harel et UML.