Machine à états finis

Le langage de modélisation unifié (UML) possède 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 des machines de Mealy et des machines de Moore . Elles prennent en charge les actions qui dépendent à la fois de l'état du système et de l' événement déclencheur , comme dans les machines de Mealy, ainsi que les actions d'entrée et de sortie , qui sont associées à des états plutôt qu'à des transitions, comme dans les machines de Moore.

Le langage de spécification et de description est une norme de l'UIT qui inclut des symboles graphiques pour décrire les actions dans la transition :

• envoyer un événement
• recevoir un événement
• démarrer un minuteur
• annuler une minuterie
• démarrer une autre machine à états simultanée
• 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.

Il existe un grand nombre de variantes pour représenter un FSM tel que celui de la figure 3.

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 l'électrotechnique , 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és dans la théorie des automates et la théorie du calcul . En informatique, les machines à états finis sont largement utilisées dans la modélisation du comportement des applications ( théorie du contrôle ), la conception de systèmes numériques matériels , l'ingénierie logicielle , les compilateurs , les protocoles réseau et la linguistique informatique .

Les machines à états finis peuvent être subdivisées en accepteurs, classificateurs, transducteurs et séquenceurs.

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 acceptant, l'entrée est acceptée ; sinon, elle est rejetée. 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 acceptant, 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 acceptant 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), tandis que l'ensemble de toutes les chaînes dont la longueur est un nombre premier ne l'est pas.

Un accepteur peut également être décrit comme définissant un langage qui contiendrait toutes les chaînes acceptées par l'accepteur mais aucune de celles rejetées ; ce langage est accepté 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 acceptant apparaît dans la Fig. 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 ₁ (qui est également l'état de départ) indique l'état dans lequel un nombre pair de 0 a été saisi. S ₁ est donc un état d'acceptation. 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 aucun 0). Des exemples de chaînes acceptées par cet accepteur sont ε (la chaîne vide ), 1, 11, 11..., 00, 010, 1010, 10110, etc.

Les classificateurs sont une généralisation des accepteurs qui produisent une sortie n- aire où n est strictement supérieur à deux.

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 les applications de contrôle et dans le domaine de la linguistique informatique .

Dans les applications de contrôle, on distingue deux types :

Machine 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érons 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:) dans l'état "Ouverture" démarre un moteur ouvrant la porte, l'action d'entrée dans 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 farineuse

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 du FSM implémenté et fonctionnera, par exemple, pour un FSM virtuel mais pas pour un FSM piloté par événement ). Il existe deux actions d'entrée (I:) : "démarrer le moteur pour fermer la porte si la commande_close arrive" et "démarrer le moteur dans l'autre sens pour ouvrir la porte si la commande_open arrive". Les états intermédiaires "ouverture" et "fermeture" ne sont pas représentés.

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 ne produisent qu'une seule séquence, qui peut être considérée comme une séquence de sortie de sorties d'accepteurs ou de transducteurs.

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 « machine à états finis combinatoire ». Elle ne permet d'effectuer des actions que lors de la transition vers un état. Ce concept est utile dans les cas où un certain nombre de machines à états finis doivent fonctionner ensemble, et lorsqu'il est pratique de considérer une partie purement combinatoire comme une forme de machine à états finis adaptée aux outils de conception.

Il existe d'autres ensembles de sémantiques disponibles pour représenter les machines d'état. Par exemple, il existe des outils de modélisation et de conception de logique pour les contrôleurs intégrés. Ils combinent des machines d'état 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 donne lieu à un formalisme et à un ensemble de sémantiques différents. Ces diagrammes, comme les machines d'état originales de Harel , prennent en charge les états imbriqués hiérarchiquement, les régions orthogonales , les actions d'état et les actions de transition.

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ù :

Pour les FSM déterministes et non déterministes, il est conventionnel de permettre à s'il s'agit d'une fonction partielle , c'est- à-dire qu'elle n'a pas besoin d'être définie pour chaque combinaison de et . Si une FSM est dans un état , le symbole suivant est et n'est pas défini, alors on peut annoncer une erreur (c'est-à-dire rejeter l'entrée). Ceci est utile dans les définitions de machines à états générales, 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 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. Autrement dit, 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ù :

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 dépend uniquement 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 fonction de sortie est appelée semi-automate ou système de transition .

Si nous négligeons le 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 l'état de Moore de destination. La transformation inverse est moins simple car un état de machine de Mealy peut avoir des étiquettes de sortie différentes sur ses transitions entrantes (arêtes). Chaque état de ce type doit être divisé en plusieurs états de machine de Moore, un pour chaque symbole de sortie incident.

Optimiser un FSM signifie trouver une machine avec le nombre minimum d'états qui exécute la même fonction. L'algorithme le plus rapide connu 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és en temps linéaire .

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 implémentation 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 de Medvedev , la sortie est directement connectée aux bascules d'état, minimisant ainsi le délai entre les bascules et la sortie.

Grâce au codage d'état pour les machines à état à faible consommation, il est possible d'optimiser la consommation d'énergie.

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énements
• Machine virtuelle à états finis
• Modèle de conception d'état

Les automates finis sont souvent utilisés dans l' interface des compilateurs de langages de programmation. Une telle interface peut comprendre plusieurs machines à états finis qui implémentent un analyseur lexical et un analyseur syntaxique. À 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 construit un arbre syntaxique. L'analyseur lexical et l'analyseur syntaxique gèrent les parties régulières et sans contexte de la grammaire du langage de programmation.