Ich möchte eine FSM schreiben, die mit einem Leerlaufzustand beginnt und sich aufgrund eines Ereignisses von einem Zustand zu einem anderen bewegt. Ich bin nicht vertraut mit der Codierung von FSM und Google hat nicht geholfen. Schätzen Sie, ob jemand die C-Datenstruktur veröffentlichen könnte, die für dieselbe verwendet werden könnte.FSM Datenstruktur Design
Danke, syuga2012
Siehe Wikipedia für die formale Definition. Sie müssen sich für Ihren Satz von Zuständen S, Ihre Eingabe Alphabet Σ und Ihre Übergangsfunktion δ entscheiden. Die einfachste Darstellung S zu haben ist die Menge der ganzen Zahlen 0, 1, 2, ... sein, N -1, wobei N die Anzahl der Zustände ist, und für Σ die Menge der ganzen Zahlen 0, 1, 2, ..., M -1, wobei M die Anzahl der Eingänge ist, und dann δ ist nur eine große N durch M Matrix. Schließlich können Sie den Satz der akzeptierenden Zustände speichern, indem Sie ein Array von N Bits speichern, wobei das Bit 1 ist, wenn der 0-Zustand ein akzeptierender Zustand ist, oder 0, wenn es kein akzeptierender Zustand ist .
Zum Beispiel, hier ist die FSM in Abbildung 3 der Wikipedia-Artikel:
#define NSTATES 2
#define NINPUTS 2
const int transition_function[NSTATES][NINPUTS] = {{1, 0}, {0, 1}};
const int is_accepting_state[NSTATES] = {1, 0};
int main(void)
{
int current_state = 0; // initial state
while(has_more_input())
{
// advance to next state based on input
int input = get_next_input();
current_state = transition_function[current_state][input];
}
int accepted = is_accepting_state[current_state];
// do stuff
}
Grundsätzlich können Sie verwenden „wenn“ bedingte und eine Variable, die den aktuellen Zustand der FSM zu speichern.
Zum Beispiel (nur ein Konzept):
int state = 0;
while((ch = getch()) != 'q'){
if(state == 0)
if(ch == '0')
state = 1;
else if(ch == '1')
state = 0;
else if(state == 1)
if(ch == '0')
state = 2;
else if(ch == '1')
state = 0;
else if(state == 2)
{
printf("detected two 0s\n");
break;
}
}
Für anspruchsvollere Implementierung können Sie speichern Zustandsübergang in zwei dimensionales Array betrachten:
int t[][] = {{1,0},{2,0},{2,2}};
int state = 0;
while((ch = getch()) != 'q'){
state = t[state][ch - '0'];
if(state == 2){
...
}
}
wenn von FSM Sie endlichen Automaten bedeuten , und Sie mögen es einfach, verwenden Sie enums, um Ihre Zustände zu benennen und zwischen ihnen zu wechseln.
Ansonsten Funktoren verwenden. Sie können die Phantasiedefinition in der STL- oder Boost-Dokumentation nachschlagen.
Sie sind mehr oder weniger Objekte, die eine Methode haben, z.B. run() genannt, das alles ausführt, was in diesem Zustand getan werden sollte, mit dem Vorteil, dass jeder Staat seinen eigenen Bereich hat.
Wir endliche Automaten für Telcos in der Vergangenheit implementiert haben und verwenden immer ein Array von Strukturen, vorausgefüllt wie:
/* States */
#define ST_ANY 0
#define ST_START 1
: : : : :
/* Events */
#define EV_INIT 0
#define EV_ERROR 1
: : : : :
/* Rule functions */
int initialize(void) {
/* Initialize FSM here */
return ST_INIT_DONE
}
: : : : :
/* Structures for transition rules */
typedef struct {
int state;
int event;
(int)(*fn)();
} rule;
rule ruleset[] = {
{ST_START, EV_INIT, initialize},
: : : : :
{ST_ANY, EV_ERROR, error},
{ST_ANY, EV_ANY, fatal_fsm_error}
};
Ich kann den Funktionszeiger hat fn falsch deklarierte, da dies aus dem Gedächtnis ist . Im Grunde hat die Zustandsmaschine das Array nach einem relevanten Zustand und Ereignis durchsucht und die Funktion aufgerufen, die getan hat, was getan werden musste, und dann den neuen Zustand zurückgegeben.
Die spezifischen Zustände wurden zuerst und die ST_ANY-Einträge zuletzt angegeben, da die Priorität der Regeln von ihrer Position im Array abhing. Die erste Regel, die gefunden wurde, war diejenige, die verwendet wurde.
Außerdem erinnere ich mich, dass wir eine Reihe von Indizes auf die erste Regel für jeden Zustand hatten, um die Suche zu beschleunigen (alle Regeln mit dem gleichen Ausgangszustand wurden gruppiert).
Denken Sie auch daran, dass dies reines C war - vielleicht gibt es einen besseren Weg, es mit C++ zu machen.
Wir verwendeten einen sehr ähnlichen Ansatz für einige der Code, mit denen ich arbeitete an meinem vorherigen Job, und es war wunderbar zu arbeiten mit. Ich vermisse es. – hlovdal
Ein paar Jungs von AT & T, jetzt bei Google, schrieb eine der besten FSM-Bibliotheken für den allgemeinen Gebrauch. Schau es dir hier an, es heißt OpenFST.
Es ist schnell, effizient und sie erstellt eine sehr klare Reihe von Operationen, die Sie auf den FSMs durchführen können, um Dinge zu minimieren oder zu determinieren, um sie für reale Probleme noch nützlicher zu machen.
Eine endliche Zustandsmaschine besteht aus einer endlichen Anzahl diskreter Zustände (ich kenne pedantisch, aber immer noch), die allgemein als ganzzahlige Werte dargestellt werden können. In c oder C++ mit einer Aufzählung ist sehr üblich.
Die Maschine reagiert auf eine endliche Anzahl von Eingängen, die oft mit einer anderen ganzzahligen Variablen dargestellt werden können. In komplizierteren Fällen können Sie eine Struktur verwenden, um den Eingabezustand darzustellen.
Jede Kombination aus internem Zustand und externer Eingabe bewirkt die Maschine:
Ein einfacher Fall in c in einem anderen Zustand übergehen könnte so aussehen Diese
enum state_val {
IDLE_STATE,
SOME_STATE,
...
STOP_STATE
}
//...
state_val state = IDLE_STATE
while (state != STOP_STATE){
int input = GetInput();
switch (state) {
case IDLE_STATE:
switch (input) {
case 0:
case 3: // note the fall-though here to handle multiple states
write(input); // no change of state
break;
case 1:
state = SOME_STATE;
break
case 2:
// ...
};
break;
case SOME_STATE:
switch (input) {
case 7:
// ...
};
break;
//...
};
};
// handle final output, clean up, whatever
obwohl dies schwer zu lesen und mo wieder leicht in mehrere Funktion von so etwas wie aufgeteilt:
while (state != STOP_STATE){
int input = GetInput();
switch (state) {
case IDLE_STATE:
state = DoIdleState(input);
break;
// ..
};
};
mit der Komplexität jeder in seiner eigenen Funktion gehaltenen Zustand.
Wie m3rLinEz says können Sie Übergänge in einem Array für die schnelle Indizierung halten. Sie können den Funktionszeiger auch in einem Array halten, um die Aktionsphase effizient zu handhaben. Dies ist besonders nützlich für die automatische Generierung von großen und komplexen Zustandsmaschinen.
Die Antworten hier scheinen sehr komplex (aber genau, trotzdem.) Also hier sind meine Gedanken.
Zuerst mag ich Dmckees (operative) Definition eines FSM und wie sie für die Programmierung gelten.
ein endlicher Automat besteht aus einer endlichen Anzahl diskreter von Zuständen (I pedantic wissen, aber immer noch), kann die allgemein als ganzzahlige Werte dargestellt werden . In c oder C++ mit einer Enumeration ist sehr üblich.
Die Maschine reagiert auf eine endliche Anzahl der Eingänge, die oft mit einer anderen Ganzzahl Wertvariable dargestellt werden kann. In komplizierteren Fällen können Sie eine Struktur verwenden, um den Eingangszustand darzustellen.
- möglicherweise in einem anderen Zustand übergehen
- möglicherweise einige Ausgabe
erzeugen Sie einen So haben:
Jede Kombination aus internem Zustand und externen Eingang wird die Maschine verursachen Programm. Es hat Zustände, und es gibt eine endliche Anzahl von ihnen. ("Die Glühbirne ist hell" oder "Die Glühbirne ist dunkel" oder "Die Glühbirne ist aus." 3 Zustände. endlich.) Ihr Programm kann immer nur in einem Zustand sein.
Also sagen Sie, dass Ihr Programm die Zustände ändern soll. Normalerweise möchten Sie etwas passieren, um eine Statusänderung auszulösen. In diesem Beispiel nehmen wir Benutzereingaben, um den Zustand zu bestimmen - sagen wir, einen Tastendruck.
Vielleicht möchten Sie Logik wie folgt. Wenn der Benutzer eine Taste drückt:
Offensichtlich statt „Austausch einer Glühlampe“, man könnte „die Textfarbe zu ändern“ oder was auch immer es ist, Sie Programm tun muss. Bevor Sie beginnen, sollten Sie Ihre Status definieren.
suchen also irgend pseudoish C-Code:
/* We have 3 states. We can use constants to represent those states */
#define BULB_OFF 0
#define BULB_DIM 1
#define BULB_BRIGHT 2
/* And now we set the default state */
int currentState = BULB_OFF;
/* now we want to wait for the user's input. While we're waiting, we are "idle" */
while(1) {
waitForUserKeystroke(); /* Waiting for something to happen... */
/* Okay, the user has pressed a key. Now for our state machine */
switch(currentState) {
case BULB_OFF:
currentState = BULB_DIM;
break;
case BULB_DIM:
currentState = BULB_BRIGHT;
doCoolBulbStuff();
break;
case BULB_BRIGHT:
currentState = BULB_OFF;
break;
}
}
Und voila. Ein einfaches Programm, das den Zustand ändert.
Dieser Code führt nur einen kleinen Teil der switch Aussage - in Abhängigkeit von dem aktuellen Zustand. Dann aktualisiert es diesen Zustand. So arbeiten FSMs.
sind nun hier einige Dinge, die Sie tun können:
Offensichtlich ist dieses Programm ändert sich nur die currentState Variable. Sie möchten, dass Ihr Code bei einer Statusänderung etwas Interessanteres macht. Die doCoolBulbStuff() Funktion könnte, ich weiß nicht, tatsächlich ein Bild von einer Glühbirne auf einem Bildschirm. Oder so.
Dieser Code sucht nur nach einem Tastendruck. Aber Ihr FSM (und damit Ihre switch-Anweisung) kann den Zustand basierend auf dem auswählen, was der Benutzer eingegeben hat (z. B. "O" bedeutet "aus"), anstatt nur zu dem nächsten in der Sequenz zu gehen.)
Teil Ihrer Frage nach einer Datenstruktur gefragt.
Eine Person schlug vor, einen Status enum zu verfolgen. Dies ist eine gute Alternative zu der #defines, die ich in meinem Beispiel verwendet habe. Die Leute haben auch Arrays vorgeschlagen - und diese Arrays verfolgen die Übergänge zwischen Zuständen. Dies ist auch eine feine Struktur zu verwenden.
Angesichts der oben genannten, nun, Sie könnten jede Art von Struktur (etwas baumähnlich, ein Array, irgendetwas) verwenden, um die einzelnen Zustände zu verfolgen und zu definieren, was in jedem Staat zu tun ist (daher einige der Vorschläge zu Verwenden Sie "Funktionszeiger" - weisen Sie einem Funktionszeiger eine Statuszuordnung zu, die angibt, was in diesem Zustand zu tun ist.)
Hoffe, dass hilft!
Sie könnten Interesse an Ragel (http://www.complan.org/ragel/), einem State Machine Compiler, der C-Code generieren kann. Wenn es Ihren Zwecken nicht entspricht, ist vielleicht der generierte Code von Interesse. – sris
bezogen http://StackOverflow.com/Questions/1647631/C-State-Machine-Design/1651187 – jldupont