Version imprimable
Salut,
Je voudrais faire une FSM (Finite State Machine) en C. Je sais qu'il existe une implémentation basée sur des tables de configurations (états - transitions). J'ai fait quelques recherches sur google mais sans succès. Je suis également intéressé par d'autres implémentations. J'ai réalisé le design pattern STATE du GOF en C au lieu de C++ c'est souple d'emploi mais le code n'est pas très joli.
Qu'avez vous à proposer?
Merci
http://emmanuel-delahaye.developpez.com/clib.htmCitation:
Envoyé par funtix
Module FSM
cool merci :D
D'autres implémentations connues ?
Si ça ne te plait pas, fait le toi même...Citation:
Envoyé par funtix
Pas de probleme, c'est exactement ce que je demandais. C'est basé sur une table de configuration. Je l'utilise dans mon projet. Mais je suis de nature curieuse et j'avais trouvé le design pattern GOF interessant. Donc, je reste ouvert à d'autres solutions...Citation:
Envoyé par Emmanuel Delahaye
Je n'en connais pas de plus rapide et de plus simple à mettre en oeuvre.Citation:
Envoyé par funtix
Je n'arrive pas a modeliser mon système avec cette machine d'état.
Je ne connais pas la theorie qui tourne autour des FSM mais je sais qu'il y a des limites/contraintes à respecter. Quelles sont-elles?
Il existe des astuces pour contourner ces eventuelles limites ?
Fait péter les specs. :!: on va être hors sujet...Citation:
Envoyé par funtix
Il existe des astuces pour contourner ces eventuelles limites ?Citation:
Je ne connais pas la theorie qui tourne autour des FSM mais je sais qu'il y a des limites/contraintes à respecter. Quelles sont-elles?
Le F de FSM est lourd de conséquences...
Tu as lu ça ?
http://emmanuel-delahaye.developpez....um.htm#theorie
Si vous n'avez pas peur de faire une "usine à gaz", il existe la possibilité de modéliser la machien d'état en XMLCitation:
Qu'avez vous à proposer?
http://www.w3.org/TR/2005/WD-scxml-20050705/
Ensuite, il est possible de parser cela en langage C.
Pour être honnête, je ne sais pas ce que cela vaut...
Tu peux utiliser les pointeurs pour representer ta machine sous forme de graphe
Oui je l'ai bien lu.Citation:
Envoyé par Emmanuel Delahaye
Pour ce qui est de la spec, je prepare ca. Ca viendra demain ou ce week end.
Le probleme est le suivant :
1 état (A) peut amener à 2 etats distincts (B et C) suivant une meme transition. C'est logique que l'automate ne puisse pas déterminer lequel d'état (B ou C) il faut choisir.
Pour determiner si c'est B ou C il faut une memoire, un contexte de ce qui s'est passé avant. Il faudrait empiler les états au fur et a mesure de l'evolution du systeme.
Je parlais de contournement, parce que dans la lib, la fonction FSM_engine peut recevoir un pointeur sur des données user (une pile par exemple mais c'est un peu compliqué, j'ai juste besoin de sauvegarder l'etat n-1) et ces données peuvent être exploiter par la suite.
What the frell is that ? Tu travailles sans specs ? Je rêve ?Citation:
Envoyé par funtix
Alors ce n'est pas la même transition. Point. Revoir l'étude préalable.Citation:
Le probleme est le suivant :
1 état (A) peut amener à 2 etats distincts (B et C) suivant une meme transition.
Tu me parles réalisation et bidouille. Ca ne m'intéresse pas. Ce que je veux ce sont les specs. Quel problème as-tu à résoudre ? C'est là dessus qu'il faut travailler. Il ne faut pas commencer à bricoler les états dans les transitions, car on ne s'en sort plus.Citation:
C'est logique que l'automate ne puisse pas déterminer lequel d'état (B ou C) il faut choisir.
Pour determiner si c'est B ou C il faut une memoire, un contexte de ce qui s'est passé avant. Il faudrait empiler les états au fur et a mesure de l'evolution du systeme.
Je parlais de contournement, parce que dans la lib, la fonction FSM_engine peut recevoir un pointeur sur des données user (une pile par exemple mais c'est un peu compliqué, j'ai juste besoin de sauvegarder l'etat n-1) et ces données peuvent être exploiter par la suite.
Je travaille pas sans spec :aie: mais je ne peux pas les mettre comme ca sur le net :mrgreen: Et puis hors contexte ca risque d'etre dur a comprendre...
Si je me souviens bien, un automate fini déterministe ne peut, et n'a qu'un seul état à la fois. Un Automate fini non-déterministe peut avoir autant d'états qu'il le veut, donc aucun problème.Citation:
Envoyé par funtix
FYI: Il est possible de "déterminiser" un automate fini non-déterministe de N états en un automate déterministe d'au maximum 2^N (ou 2^N-1, sais plus) états.
Effectivement, c'est l'idée que j'ai eu hier soir et que j'ai implémenté ce matin.Citation:
Envoyé par Médinoc
Le problème : une meme transition peut amener a 2 etats differents. Ce qui permet de choisir entre l'une et l'autre c'est l'etat n-1.
L'idée donc, c'est d'integrer l'etat n-1 dans le systeme a modeliser. Pour ce faire, j'ai creer des etats supplémentaires.
Ainsi mon systeme initial avait 5 états. Avec la modelisation de ce matin, j'ai 12 états (c-a-d 7 etats supplémentaires).
Ca semble fonctionnait.
Il faut que j'ajoute quelques TU pour etre bien sur.
Par contre je ne sais pas dire si mon systeme initial est déterministe ou non. Je ne vois pas ce qu'il y a de non deterministe pour ne pas avoir reussi a le modeliser la premiere fois. Je pense que le systeme etait simplement mal decrit/specifier.
Si ca interesse du monde je pourrais publier les resultats dans les jours a venir...
Merci de votre aide.
ps : Le site cité au départ (que je m'avait été deja donné suite à une question sur la conception en c) est une tres bonne source d'informations.
Euh...Citation:
Envoyé par funtix
On va remettre ça à plat pour être sûr qu'on parle de la même chose : C'est pour passer de l'état N-1 à l'état N que tu dis ça ou pour passer de l'état N à l'état N+1 ?
Si c'est le premier cas, c'est une erreur de terme. Une transistion n'est pas le message mais l'ensemble (état, message). Et cela, ça donne bien une flèche bien définie, partant d'un état précis vers seul un autre état précis (Sur un AFD) et sur un message précis. Ça, je suppose que c'est déjà géré par l'implémentation d'Emmanuel, car sinon ce ne serait pas une vraie bibliothèque d'AFD...
Si c'est le second cas, alors tu as mal décomposé ta machine: Tu as regroupé à l'état N deux états différents.
Illustration du problème (L'etat courant est en gras)
e1 e2
Etat1 ----> Etat2 ----> Etat3
e1 e2
Etat1' ----> Etat2 ----> Etat3'
Dans cette exemple, on voit que l'Etat2 peut mener à 2 états differents avec le même évènement (e2).
Pour que l'automate sache dans quel etat il doit aller (Etat3 ou Etat3') il doit regarder l'etat n-1 c'est a dire regarder si l'on vient de Etat1 ou Etat1'.
Pour résoudre ce problème, j'ai crée des états supplémentaires.
Dans la précédente modélisation, les états étaient : Etat1, Etat1', Etat2, Etat3, Etat3'
Dans la nouvelle modélisation, j'ai les états :
Etat1, Etat1', Etat1_Etat2, Etat1'_Etat2, Etat3, Etat3'
On voit que l'état2 est scindé en 2: Selon la provenance.
J'espère que je me suis fait comprendre.
Je pense oui!Citation:
Si c'est le second cas, alors tu as mal décomposé ta machine: Tu as regroupé à l'état N deux états différents.
Citation:
Par contre je ne sais pas dire si mon systeme initial est déterministe ou non. Je ne vois pas ce qu'il y a de non deterministe pour ne pas avoir reussi a le modeliser la premiere fois. Je pense que le systeme etait simplement mal decrit/specifier.
Problème de conception. Soit il manque un état (C'est pas Etat2, mais Etat2'),Citation:
Envoyé par funtix
soit il manque un évènement (mais ça, c'est généralement du ressort de la spécification et non de la conception).Code:
2
3
4
5
6e1 e2 Etat1 ----> Etat2 ----> Etat3 e1 e2 Etat1' ----> Etat2'----> Etat3'
Moi ca me parait tout a fait possible. Un evenement intervenant dans 2 etats differents peut tres bien provoquer le passage a un meme etat.
Mais ce n'est pas le même état, puisque pour passer à l'état N+1, tu dois connaitre ce qu'il y avait à l'état N-1. Cela signifie que l'état N est incomplet, donc une erreur.
Exact, autant pour moi.