Je cherche de bons exemples de machines à états finis; la langue n'est pas particulièrement importante, juste de bons exemples.

Les implémentations de code sont utiles (pseudo-code généralisé), mais il est également très utile de rassembler les diverses utilisations des FSM.

Les exemples n'ont pas nécessairement besoin d'être informatisés, par exemple l'exemple des réseaux ferroviaires de Mike Dunlavey, est très utile.

Un coffre-fort (événement déclenché)

• États : plusieurs états "verrouillés", un état "déverrouillé"
• Transitions : les combinaisons / touches correctes vous font passer des états verrouillés initiaux à des états verrouillés plus proches de déverrouillés, jusqu'à ce que vous arriviez enfin à déverrouillé. Des combinaisons / touches incorrectes vous ramènent dans l'état verrouillé initial (parfois appelé inactif .

Feu de circulation (heure déclenchée | capteur [événement] déclenché)

• États : ROUGE, JAUNE, VERT (exemple le plus simple)
• Transitions : après une minuterie, changez ROUGE en VERT, VERT en JAUNE et JAUNE en ROUGE. Peut également être déclenché sur la détection de voitures dans divers états (plus compliqués).

Distributeur automatique (événement déclenché, une variation du coffre - fort )

• États : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS, etc., VEND, CHANGE
• Transitions : Modifiez l'état lors de l'insertion des pièces, des billets, passez à VEND lorsque le montant d'achat est correct (ou plus), puis passez à CHANGE ou IDLE (selon l'éthique de votre distributeur automatique)

Exemple de protocole de passerelle de frontière

BGP est un protocole qui soutient les principales décisions de routage sur Internet. Il maintient une table pour déterminer l'accessibilité des hôtes à partir d'un nœud donné et a rendu Internet vraiment décentralisé.

Dans le réseau, chaque nœud BGP est un homologue et utilise une machine à états finis, avec l'un des six états Inactif , Connect , Actif , OpenSent , OpenConfirm et Established . Chaque connexion homologue du réseau conserve l'un de ces états.

Le protocole BGP détermine les messages qui sont envoyés aux pairs afin de changer leur état.

Statechart BPG.

Tourner au ralenti

Le premier état inactif . Dans cet état, BGP initialise les ressources, refuse les tentatives de connexion entrantes et établit une connexion avec l'homologue.

Relier

Le deuxième état Connect . Dans cet état, le routeur attend la fin de la connexion et passe à l' état OpenSent en cas de succès. En cas d'échec, il réinitialise le minuteur ConnectRetry et passe à l' actif état à l'expiration.

actif

Dans l' état Actif , le routeur remet à zéro le temporisateur ConnectRetry et revient à l' état Connect .

OpenSent

Dans l' état OpenSent , le routeur envoie un message Open et en attend un en retour. Les messages Keepalive sont échangés et, une fois la réception réussie, le routeur est placé dans l' état Established .

Établi

Dans l' état établi , le routeur peut envoyer / recevoir: Keepalive; Mise à jour; et des messages de notification vers / depuis son homologue.

Plus d' informations sur BGP sont sur wikipedia

Ils sont utiles pour modéliser toutes sortes de choses. Par exemple, un cycle électoral peut être modélisé avec des États sur le modèle de (gouvernement normal) - élection appelée -> (campagne précoce) - Parlement dissous -> (campagne intensive) - élection -> (dépouillement des votes ). Puis soit (dépouillement des votes) - pas de majorité -> (négociations de coalition) - accord atteint -> (gouvernement normal) ou (dépouillement des votes) - majorité -> (gouvernement normal). J'ai implémenté une variante de ce schéma dans un jeu avec un sous-jeu politique.

Ils sont également utilisés dans d'autres aspects des jeux: l'IA est souvent basée sur l'état; les transitions entre les menus et les niveaux, et les transitions au décès ou au niveau terminé sont souvent bien modélisées par les FSM.

L'analyseur CSV utilisé dans le plug-in jquery-csv

C'est un analyseur grammatical de base de Chomsky Type III .

Un tokenizer regex est utilisé pour évaluer les données caractère par caractère. Lorsqu'un caractère de contrôle est rencontré, le code est transmis à une instruction switch pour une évaluation plus approfondie basée sur l'état de départ. Les caractères non contrôlés sont regroupés et copiés en masse pour réduire le nombre d'opérations de copie de chaîne nécessaires.

Le tokenizer:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

Le premier jeu de correspondances est constitué des caractères de contrôle: séparateur de valeurs (") séparateur de valeurs (,) et séparateur d'entrée (toutes les variantes de la nouvelle ligne). La dernière correspondance gère le regroupement de caractères non contrôlés.

L'analyseur doit respecter 10 règles:

• Règle n ° 1 - Une entrée par ligne, chaque ligne se termine par une nouvelle ligne
• Règle n ° 2 - saut de ligne à la fin du fichier omis
• Règle n ° 3 - La première ligne contient des données d'en-tête
• Règle n ° 4 - Les espaces sont considérés comme des données et les entrées ne doivent pas contenir de virgule de fin
• Règle n ° 5 - Les lignes peuvent ou non être délimitées par des guillemets doubles
• Règle n ° 6 - Les champs contenant des sauts de ligne, des guillemets doubles et des virgules doivent être placés entre guillemets doubles
• Règle n ° 7 - Si des guillemets doubles sont utilisés pour entourer des champs, un guillemet double apparaissant à l'intérieur d'un champ doit être échappé en le précédant d'un autre guillemet double
• Amendement n ° 1 - Un champ non cité peut ou peut
• Amendement n ° 2 - Un champ cité peut ou non
• Amendement n ° 3 - Le dernier champ d'une entrée peut ou non contenir une valeur nulle

Remarque: Les 7 principales règles sont dérivées directement de l' IETF RFC 4180 . Les 3 derniers ont été ajoutés pour couvrir les cas marginaux introduits par les applications de feuille de calcul modernes (ex Excel, Google Spreadsheet) qui ne délimitent pas (c.-à-d. Citent) toutes les valeurs par défaut. J'ai essayé de contribuer aux modifications du RFC mais je n'ai toujours pas entendu de réponse à ma demande.

Assez avec la liquidation, voici le diagramme:

États:

1. état initial d'une entrée et / ou d'une valeur
2. une citation d'ouverture a été rencontrée
3. une deuxième citation a été rencontrée
4. une valeur non cotée a été rencontrée

Transitions:

• une. vérifie les valeurs entre guillemets (1), les valeurs sans guillemets (3), les valeurs nulles (0), les entrées nulles (0) et les nouvelles entrées (0)
• b. vérifie un deuxième caractère de devis (2)
• c. vérifie la citation échappée (1), la fin de la valeur (0) et la fin de l'entrée (0)
• ré. vérifie la fin de la valeur (0) et la fin de l'entrée (0)

Remarque: il manque en fait un état. Il devrait y avoir une ligne de 'c' -> 'b' marquée avec l'état '1' car un deuxième délimiteur échappé signifie que le premier délimiteur est toujours ouvert. En fait, il serait probablement préférable de le représenter comme une autre transition. La création de ceux-ci est un art, il n'y a pas une seule façon correcte.

Remarque: il manque également un état de sortie mais sur des données valides, l'analyseur se termine toujours lors de la transition 'a' et aucun des états n'est possible car il ne reste plus rien à analyser.

La différence entre les États et les transitions:

Un état est fini, ce qui signifie qu'il ne peut être déduit que pour signifier une chose.

Une transition représente le flux entre les états et peut donc signifier beaucoup de choses.

Fondamentalement, la relation état-> transition est 1 -> * (c'est-à-dire un à plusieurs). L'État définit «ce que c'est» et la transition définit «comment c'est géré».

Remarque: Ne vous inquiétez pas si l'application d'états / transitions ne semble pas intuitive, elle n'est pas intuitive. Il a fallu des correspondances approfondies avec quelqu'un de bien plus intelligent que moi avant de finalement avoir le concept.

Le pseudo-code:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Remarque: c'est l'essentiel, dans la pratique, il y a beaucoup plus à considérer. Par exemple, la vérification des erreurs, les valeurs nulles, une ligne vide de fin (c'est-à-dire qui est valide), etc.

Dans ce cas, l'état est l'état des choses lorsque le bloc de correspondance d'expression régulière termine une itération. La transition est représentée par les instructions case.

En tant qu'êtres humains, nous avons tendance à simplifier les opérations de bas niveau en des résumés de niveau supérieur, mais travailler avec un FSM, c'est travailler avec des opérations de bas niveau. Bien que les états et les transitions soient très faciles à travailler individuellement, il est intrinsèquement difficile de visualiser le tout d'un coup. J'ai trouvé plus facile de suivre les chemins individuels d'exécution encore et encore jusqu'à ce que je puisse comprendre comment les transitions se déroulent. C'est comme apprendre des mathématiques de base, vous ne pourrez pas évaluer le code à partir d'un niveau supérieur jusqu'à ce que les détails de bas niveau deviennent automatiques.

À part: Si vous regardez la mise en œuvre réelle, il manque beaucoup de détails. Tout d'abord, tous les chemins impossibles lèveront des exceptions spécifiques. Il devrait être impossible de les toucher, mais si quelque chose se casse, ils déclencheront absolument des exceptions dans le lanceur de test. Deuxièmement, les règles de l'analyseur pour ce qui est autorisé dans une chaîne de données CSV «légale» sont assez lâches, donc le code nécessaire pour gérer un grand nombre de cas de bord spécifiques. Indépendamment de ce fait, c'était le processus utilisé pour se moquer du FSM avant toutes les corrections de bogues, les extensions et le réglage fin.

Comme avec la plupart des conceptions, ce n'est pas une représentation exacte de la mise en œuvre, mais elle décrit les parties importantes. Dans la pratique, il existe en fait 3 fonctions d'analyseur différentes dérivées de cette conception: un séparateur de ligne spécifique au csv, un analyseur à ligne unique et un analyseur à lignes multiples complet. Ils fonctionnent tous de manière similaire, ils diffèrent dans la façon dont ils traitent les caractères de nouvelle ligne.

FSM simple en Java

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Voilà. OK, ce n'est pas brillant, mais ça montre l'idée.

Vous trouverez souvent des FSM dans les produits de télécommunications car ils offrent une solution simple à une situation par ailleurs complexe.

J'ai trouvé que penser / modéliser un ascenseur (ascenseur) est un bon exemple de machine à états finis. Il nécessite peu d'introduction, mais offre une situation loin d'être triviale à mettre en œuvre.

Les états sont, par exemple, au rez-de-chaussée, au premier étage, etc.

L'effet des boutons dans la cage d'ascenseur et aux étages eux-mêmes fournit des entrées, dont l'effet dépend à la fois du bouton enfoncé et de l'état actuel.

Chaque étage, à l'exception du haut et du bas, aura deux boutons: l'un pour demander à l'ascenseur de monter, l'autre pour descendre.

OK, voici un exemple. Supposons que vous souhaitiez analyser un entier. Cela irait quelque chose comme dd*où dest un chiffre entier.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Bien sûr, comme l'a dit @Gary, vous pouvez masquer ces gotos au moyen d'une instruction switch et d'une variable d'état. Notez que cela peut être structuré en ce code, qui est isomorphe à l'expression régulière d'origine:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Bien sûr, vous pouvez également le faire avec une table de recherche.

Les machines à états finis peuvent être réalisées de plusieurs façons, et de nombreuses choses peuvent être décrites comme des instances de machines à états finis. Ce n'est pas tant une «chose» qu'un concept, pour penser aux choses.

Exemple de réseau ferroviaire

Un exemple de FSM est un réseau ferroviaire.

Il existe un nombre fini de commutateurs où un train peut emprunter l'une des deux voies.

Il existe un nombre fini de pistes reliant ces commutateurs.

A tout moment, un train est sur une voie, il peut être envoyé sur une autre voie en traversant un aiguillage, sur la base d'un seul bit d'information d'entrée.

Machine à états finis en rubis:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

C'est le comportement d'un seul nœud de calcul dans un système distribué, mettant en place un schéma de communication basé sur des liaisons. Plus ou moins. Sous forme graphique, cela ressemble à ceci:

Consultez ce lien pour quelques exemples simples d'analyse lexicale (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

Vous pouvez également consulter le "livre du dragon" pour des exemples (ce n'est pas une lecture légère)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

En pratique, les State Machines sont souvent utilisées pour:

• Objectifs de conception (modélisation des différentes actions dans un programme)
• Analyseurs de langage naturel (grammaire)
• Analyse de chaîne

Un exemple serait une machine d'état qui scanne une chaîne pour voir si elle a la bonne syntaxe. Les codes postaux néerlandais par exemple sont au format "1234 AB". La première partie ne peut contenir que des chiffres, la seconde uniquement des lettres. Une machine d'état pourrait être écrite pour savoir si elle est à l'état NUMBER ou à l'état LETTER et si elle rencontre une mauvaise entrée, la rejeter.

Cette machine d'état accepteur a deux états: numérique et alpha. La machine d'état démarre à l'état numérique et commence à lire les caractères de la chaîne à vérifier. Si des caractères non valides sont rencontrés pendant l'un des états, la fonction retourne avec une valeur False, rejetant l'entrée comme non valide.

Code Python:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        elif char not in string.digits:
            return False
    elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Source: (Finite-) State Machines en pratique