Quiero escribir un FSM que comience con un estado inactivo y se mueva de un estado a otro en función de algún evento. No estoy familiarizado con la codificación de FSM y Google no me ayudó. Apreciar si alguien puede publicar la estructura de datos C que podría usarse para la misma.Diseño de estructura de datos FSM
Gracias, syuga2012
Ver Wikipedia para la definición formal. Debe decidir sobre su conjunto de estados S, su alfabeto de entrada Σ y su función de transición δ. La representación más sencilla es tener S ser el conjunto de los números enteros 0, 1, 2, ..., N -1, donde N es el número de estados, y por Σ ser el conjunto de los enteros 0, 1, 2, ..., M -1, donde M es el número de entradas y, a continuación δ es sólo un gran N por M matriz . Por último, puede almacenar el conjunto de estados de aceptación mediante el almacenamiento de una matriz de N bits, donde el i ésimo bit es 1 si el ésimo estado i es un estado de aceptación, o 0 si no es un estado de aceptación .
Por ejemplo, aquí es el FSM en la figura 3 del artículo de Wikipedia:
#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
}
Básicamente puede utilizar "si" condicional y una variable para almacenar el estado actual de la FSM.
Por ejemplo (sólo un concepto):
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;
}
}
para una aplicación más sofisticada, puede considerar la transición de estados tienda en matriz de dos dimensiones:
int t[][] = {{1,0},{2,0},{2,2}};
int state = 0;
while((ch = getch()) != 'q'){
state = t[state][ch - '0'];
if(state == 2){
...
}
}
si por FSM quiere decir máquina de estados finitos , y te gusta simple, usa enumeraciones para nombrar tus estados y cambiar entre ellos.
De lo contrario utilice funtores. Puede ver la definición de lujo en la stl o impulsar documentos.
Son más o menos objetos, que tienen un método , p. llamado run(), que ejecuta todo lo que se debe hacer en ese estado, , con la ventaja de que cada estado tiene su propio alcance .
Hemos implementado máquina de estados finitos para las empresas de telecomunicaciones en el pasado y siempre se utiliza una matriz de estructuras, pre-poblado como:
/* 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}
};
que pueden tener la función de puntero fn declaró equivocada ya que se trata de la memoria . Básicamente, la máquina de estado buscó en la matriz un estado y evento relevante y llamó a la función que hizo lo que tenía que hacer y luego devolvió el nuevo estado.
Los estados específicos se pusieron primero y las entradas ST_ANY duran ya que la prioridad de las reglas dependía de su posición en la matriz. La primera regla que se encontró fue la utilizada.
Además, recuerdo que teníamos una serie de índices de la primera regla para que cada estado agilizara las búsquedas (todas las reglas con el mismo estado inicial se agruparon).
También tenga en cuenta que esto era pura C - puede haber una mejor manera de hacerlo con C++.
Utilizamos un enfoque muy similar para algunos de los códigos con los que estaba trabajando en mi trabajo anterior, y fue maravilloso trabajar con. Lo extraño. – hlovdal
Algunos chicos de AT & T, ahora en Google, escribieron una de las mejores bibliotecas de FSM disponibles para uso general. Compruébalo aquí, se llama OpenFST.
Es rápido, eficiente, y crearon un conjunto muy claro de operaciones que puede realizar en los FSM para hacer cosas como minimizarlas o determinarlas para hacerlas aún más útiles para problemas del mundo real.
Una máquina de estados finitos consiste en un número finito discreto de estados (lo sé pedante, pero aún), que generalmente se puede representar como valores enteros. En c o C++ usar una enumeración es muy común.
La máquina responde a un número finito de entradas que a menudo se puede representar con otra variable de valor entero. En casos más complicados puede usar una estructura para representar el estado de entrada.
Cada combinación de estado interno y entrada externa hará que la máquina para:
un caso simple en c podría ser como esto
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
aunque esto es difícil de leer y mo re fácilmente dividir en función múltiple por algo como:
while (state != STOP_STATE){
int input = GetInput();
switch (state) {
case IDLE_STATE:
state = DoIdleState(input);
break;
// ..
};
};
con las complejidades de cada estado que tuvo lugar en su propia función.
Como m3rLinEz says, puede mantener las transiciones en una matriz para una indexación rápida. También puede mantener el puntero de función en una matriz para manejar eficientemente la fase de acción. Esto es especialmente útil para la generación automática de máquinas de estado grandes y complejas.
Las respuestas aquí parecen realmente complejas (pero precisas, no obstante.) Así que aquí están mis pensamientos.
Primero, me gusta la definición (operativa) de dmckee de un FSM y cómo se aplican a la programación.
Una máquina de estado finito se compone de un número discreto finito de estados (I sé pedante, pero todavía), que puede generalmente ser representado como un número entero valores. En c o C++ usando una enumeración es muy común.
La máquina responde a una finito número de entradas que puede a menudo ser representados con otra variable valorada número entero . En los casos más complicados puede utilizar una estructura para representar el estado de entrada.
Cada combinación de estado interno y entrada externa hará que la máquina a:
- posiblemente transición a otro estado
- posiblemente generar alguna salida
para que tenga una programa. Tiene estados, y hay un número finito de ellos. ("la bombilla es brillante" o "la bombilla está apagada" o "la bombilla está apagada". 3 indica "finito"). Su programa solo puede estar en un estado a la vez.
Por lo tanto, supongamos que quiere que su programa cambie de estado. Por lo general, querrá que algo al pase para activar un cambio de estado. En este ejemplo, qué tal si tomamos la entrada del usuario para determinar el estado, por ejemplo, presionando una tecla.
Es posible que desee una lógica como esta. Cuando el usuario presiona una tecla:
Obviamente, en lugar de "sustituir una lámpara", es posible que "cambiar el color del texto" o lo que sea que el programa tiene que hacer. Antes de comenzar, querrá definir sus estados.
Así que buscando en algún código pseudoish C:
/* 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;
}
}
Y, voila. Un programa simple que cambia el estado.
Este código ejecuta solo una pequeña parte de la instrucción switch, según el estado actual. Entonces actualiza ese estado. Así es como funcionan los FSM.
Ahora aquí hay algunas cosas que puede hacer:
Obviamente, este programa sólo cambia la variable currentState. Querrá que su código haga algo más interesante en un cambio de estado. La función doCoolBulbStuff() podría, no sé, poner realmente una imagen de una bombilla en una pantalla. O algo.
Este código solo busca una pulsación de tecla. Pero su FSM (y por lo tanto su declaración de cambio) puede elegir estado en función de lo que ingresó el usuario (por ejemplo, "O" significa "ir a apagado" en lugar de simplemente ir a lo que sea siguiente en la secuencia.)
Parte de su pregunta pidió una estructura de datos.
Una persona sugirió usar un enum para realizar un seguimiento de los estados. Esta es una buena alternativa al #defines que utilicé en mi ejemplo. La gente también ha estado sugiriendo matrices, y estas matrices llevan un registro de las transiciones entre estados. Esta es también una buena estructura para usar.
Dado lo anterior, bien, podría usar cualquier tipo de estructura (algo similar a un árbol, una matriz, cualquier cosa) para realizar un seguimiento de los estados individuales y definir qué hacer en cada estado (de ahí algunas sugerencias para utilice "punteros a funciones": tenga un mapa de estado con un puntero a función que indique qué hacer en ese estado)
Espero que ayude!
Puede que le interese Ragel (http://www.complang.org/ragel/) que es un compilador de máquina de estados que puede generar código C. Si no cumple sus propósitos, tal vez el código generado sea de interés. – sris
relacionado http://stackoverflow.com/questions/1647631/c-state-machine-design/1651187 – jldupont