state machines - resueltos - usos para máquinas de estado

maquinas de estado mealy y moore

Question

¿En qué áreas de programación usaría máquinas de estado? Por qué ? ¿Cómo podría implementar uno?

EDITAR: por favor, brinde un ejemplo práctico, si no es demasiado pedir.

Answer 1

¿En qué áreas de programación usaría una máquina de estado?

Utilice una máquina de estado para representar un objeto (real o lógico) que pueda existir en un número limitado de condiciones (" estados ") y progrese de un estado al siguiente de acuerdo con un conjunto fijo de reglas.

¿Por qué debería usar una máquina de estado?

Una máquina de estado a menudo es una forma muy compacta de representar un conjunto de reglas y condiciones complejas, y procesar varias entradas. Verá máquinas de estados en dispositivos integrados que tienen memoria limitada. Implementado bien, una máquina de estado es auto-documentada porque cada estado lógico representa una condición física. Una máquina de estado puede incorporarse en una pequeña cantidad de código en comparación con su equivalente de procedimiento y funciona de manera extremadamente eficiente. Además, las reglas que rigen los cambios de estado a menudo se pueden almacenar como datos en una tabla, proporcionando una representación compacta que se puede mantener fácilmente.

¿Cómo puedo implementar uno?

Ejemplo trivial:

enum states {      // Define the states in the state machine.
  NO_PIZZA,        // Exit state machine.
  COUNT_PEOPLE,    // Ask user for # of people.
  COUNT_SLICES,    // Ask user for # slices.
  SERVE_PIZZA,     // Validate and serve.
  EAT_PIZZA        // Task is complete.
} STATE;

STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;

// Serve slices of pizza to people, so that each person gets
/// the same number of slices.   
while (state != NO_PIZZA)  {
   switch (state)  {
   case COUNT_PEOPLE:  
       if (promptForPeople(&nPeople))  // If input is valid..
           state = COUNT_SLICES;       // .. go to next state..
       break;                          // .. else remain in this state.
   case COUNT_SLICES:  
       if (promptForSlices(&nSlices))
          state = SERVE_PIZZA;
        break;
   case SERVE_PIZZA:
       if (nSlices % nPeople != 0)    // Can''t divide the pizza evenly.
       {                             
           getMorePizzaOrFriends();   // Do something about it.
           state = COUNT_PEOPLE;      // Start over.
       }
       else
       {
           nSlicesPerPerson = nSlices/nPeople;
           state = EAT_PIZZA;
       }
       break;
   case EAT_PIZZA:
       // etc...
       state = NO_PIZZA;  // Exit the state machine.
       break;
   } // switch
} // while

Notas:

• El ejemplo usa un switch() con estados explícitos de case / break para simplificar. En la práctica, un case a menudo "caerá" al siguiente estado.

• Para facilitar el mantenimiento de una máquina de estado grande, el trabajo realizado en cada case se puede encapsular en una función de "trabajador". Obtenga cualquier entrada en la parte superior del while() , páselo a la función de trabajador y verifique el valor de retorno del trabajador para calcular el siguiente estado.

• Para compacidad, todo el switch() se puede reemplazar con una serie de indicadores de función. Cada estado está incorporado por una función cuyo valor de retorno es un puntero al siguiente estado. Advertencia: Esto puede simplificar la máquina de estado o dejarla totalmente inmanejable, ¡así que considere la implementación con cuidado!

• Un dispositivo integrado puede implementarse como una máquina de estado que solo sale en un error catastrófico, después de lo cual realiza un restablecimiento completo y vuelve a entrar en la máquina de estado.

Answer 2

Algunas buenas respuestas ya. Para una perspectiva ligeramente diferente, considere buscar un texto en una cadena más grande. Alguien ya ha mencionado expresiones regulares y este es realmente solo un caso especial, aunque importante.

Considere la siguiente llamada a método:

very_long_text = "Bereshit bara Elohim et hashamayim ve''et ha''arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)

¿Cómo implementaría find_in_string ? El enfoque fácil usaría un bucle anidado, algo como esto:

for i in 0 … length(very_long_text) - length(word):
    found = true
    for j in 0 … length(word):
        if (very_long_text[i] != word[j]):
            found = false
            break
    if found: return i
return -1

¡Además del hecho de que esto es ineficiente, forma una máquina de estado ! Los estados aquí están algo escondidos; permítanme reescribir el código ligeramente para hacerlos más visibles:

state = 0
for i in 0 … length(very_long_text) - length(word):
    if very_long_text[i] == word[state]:
        state += 1
        if state == length(word) + 1: return i
    else:
        state = 0
return -1

Los diferentes estados aquí representan directamente todas las diferentes posiciones en la palabra que buscamos. Hay dos transiciones para cada nodo en el gráfico: si las letras coinciden, vaya al siguiente estado; para cada otra entrada (es decir, cada dos letras en la posición actual), regrese a cero.

Esta ligera reformulación tiene una gran ventaja: ahora se puede modificar para obtener un mejor rendimiento utilizando algunas técnicas básicas. De hecho, cada algoritmo avanzado de búsqueda de cadenas (descontando las estructuras de datos de índice por el momento) se construye en la parte superior de esta máquina de estados y mejora algunos aspectos de la misma.

Answer 3

Aquí hay un ejemplo probado y funcional de una máquina de estado. Supongamos que se encuentra en una secuencia en serie (el puerto serie, los datos tcp / ip o el archivo son ejemplos típicos). En este caso, estoy buscando una estructura de paquete específica que se pueda dividir en tres partes, sincronización, longitud y carga útil. Tengo tres estados, uno está inactivo, esperando la sincronización, el segundo es que tenemos una buena sincronización, el siguiente byte debe ser de longitud, y el tercer estado es acumular la carga útil.

El ejemplo es puramente serial con solo un búfer, ya que aquí se recuperará de un byte o paquete malo, posiblemente descartando un paquete pero finalmente recuperándose, puede hacer otras cosas como una ventana deslizante para permitir una recuperación inmediata. En este caso, cuando diga un paquete parcial que se acorta, se inicia un nuevo paquete completo, el código siguiente no detectará esto y descartará el paquete parcial y el paquete completo y se recuperará en el siguiente. Una ventana deslizante te salvaría allí si realmente necesitas procesar todos los paquetes.

Uso este tipo de máquina de estado todo el tiempo, ya sean flujos de datos en serie, tcp / ip, archivo i / o. O tal vez tcp / ip protocolos, digamos que desea enviar un correo electrónico, abrir el puerto, esperar que el servidor envíe una respuesta, enviar HELO, esperar que el servidor envíe un paquete, enviar un paquete, esperar la respuesta, Esencialmente en ese caso, así como en el caso que se muestra a continuación, puede estar inactivo esperando que entre el siguiente byte / paquete. Para recordar lo que estaba esperando, también para volver a usar el código que espera algo que pueda usar Variables de estado. De la misma manera que las máquinas de estado se usan en lógica (esperando el próximo reloj, ¿qué estaba esperando?).

Al igual que en la lógica, es posible que desee hacer algo diferente para cada estado, en este caso, si tengo un buen patrón de sincronización reinicio el desplazamiento en mi almacenamiento, así como restablecer el acumulador de suma de comprobación. El estado de la longitud del paquete muestra un caso en el que es posible que desee abortar fuera de la ruta de control normal. No todo, de hecho, muchas máquinas de estado pueden saltar o pueden recorrer la ruta normal, la siguiente es prácticamente lineal.

Espero que esto sea útil y deseo que las máquinas de estado se usen más en software.

Los datos de prueba tienen problemas intencionales con los que la máquina de estado se recupera. Hay algunos datos basura después del primer paquete bueno, un paquete con una suma de comprobación incorrecta y un paquete con una longitud no válida. Mi salida fue:

buen paquete: FA0712345678EB Patrón de sincronización inválido 0x12 Patrón de sincronización inválido 0x34 Patrón de sincronización inválido 0x56 Error de suma de comprobación 0xBF Longitud de paquete inválida 0 Patrón de sincronización inválido 0x12 Patrón de sincronización inválido 0x34 Patrón de sincronización inválido 0x56 Patrón de sincronización inválido 0x78 Patrón de sincronización inválido 0xEB buen paquete: FA081234567800EA no más prueba datos

Los dos buenos paquetes en la secuencia fueron extraídos a pesar de la mala información. Y los datos malos fueron detectados y tratados.

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

unsigned char testdata[] =
{
    0xFA,0x07,0x12,0x34,0x56,0x78,0xEB,  
    0x12,0x34,0x56,  
    0xFA,0x07,0x12,0x34,0x56,0x78,0xAA,  
    0xFA,0x00,0x12,0x34,0x56,0x78,0xEB,  
    0xFA,0x08,0x12,0x34,0x56,0x78,0x00,0xEA  
};

unsigned int testoff=0;

//packet structure  
// [0] packet header 0xFA  
// [1] bytes in packet (n)  
// [2] payload  
// ... payload  
// [n-1] checksum  
//  

unsigned int state;

unsigned int packlen;  
unsigned int packoff;  
unsigned char packet[256];  
unsigned int checksum;  

int process_packet( unsigned char *data, unsigned int len )  
{  
    unsigned int ra;  

    printf("good packet:");
    for(ra=0;ra<len;ra++) printf("%02X",data[ra]);
    printf("/n");
}  
int getbyte ( unsigned char *d )  
{  
    //check peripheral for a new byte  
    //or serialize a packet or file  

    if(testoff<sizeof(testdata))
    {
        *d=testdata[testoff++];
        return(1);
    }
    else
    {
        printf("no more test data/n");
        exit(0);
    }
    return(0);
}

int main ( void )  
{  
    unsigned char b;

    state=0; //idle

    while(1)
    {
        if(getbyte(&b))
        {
            switch(state)
            {
                case 0: //idle
                    if(b!=0xFA)
                    {
                        printf("Invalid sync pattern 0x%02X/n",b);
                        break;
                    }
                    packoff=0;
                    checksum=b;
                    packet[packoff++]=b;

                    state++;
                    break;
                case 1: //packet length
                    checksum+=b;
                    packet[packoff++]=b;

                    packlen=b;
                    if(packlen<3)
                    {
                        printf("Invalid packet length %u/n",packlen);
                        state=0;
                        break;
                    }

                    state++;
                    break;
                case 2: //payload
                    checksum+=b;
                    packet[packoff++]=b;

                    if(packoff>=packlen)
                    {
                        state=0;
                        checksum=checksum&0xFF;
                        if(checksum)
                        {
                            printf("Checksum error 0x%02X/n",checksum);
                        }
                        else
                        {
                            process_packet(packet,packlen);
                        }
                    }
                    break;
            }
        }

        //do other stuff, handle other devices/interfaces

    }
}

Answer 4

El código dirigido por el estado es una buena manera de implementar ciertos tipos de lógica (los analizadores son un ejemplo). Se puede hacer de varias maneras, por ejemplo:

• Estado controlando qué bit de código se está ejecutando en realidad en un punto determinado (es decir, el estado está implícito en la parte del código que está escribiendo). Los analizadores sintácticos de descenso recursivo son un buen ejemplo de este tipo de código.

• Estado conduciendo qué hacer en un condicional como una declaración de cambio.

• Máquinas de estados explícitos, como las generadas por herramientas de generación de analizadores, como Lex y Yacc .

No todos los códigos dirigidos por el estado se utilizan para el análisis sintáctico. Un generador de máquina de estado general es smc . Inhala una definición de máquina de estado (en su lenguaje) y escupirá código para la máquina de estados en una variedad de idiomas.

Answer 5

El patrón de diseño de estado es una forma orientada a objetos para representar el estado de un objeto por medio de una máquina de estados finitos. Por lo general, ayuda a reducir la complejidad lógica de la implementación de ese objeto (anidados si, muchos indicadores, etc.)

Answer 6

Infraestructura de QA, destinada a raspar la pantalla o ejecutar de otro modo un proceso bajo prueba. (Esta es mi área de experiencia particular: construí un framework de máquina de estado en Python para mi último empleador con soporte para empujar el estado actual a una pila y usando varios métodos de selección de controlador de estado para usar en todos nuestros raspadores de pantalla basados ​​en TTY) . El modelo conceptual encaja bien, ya que se ejecuta a través de una aplicación TTY, pasa por un número limitado de estados conocidos y puede volver a los antiguos (piense en utilizar un menú anidado). Esto ha sido liberado (con el permiso de dicho empleador); utilice Bazaar para consultar http://web.dyfis.net/bzr/isg_state_machine_framework/ si desea ver el código.

Sistemas de ticket, gestión de proceso y flujo de trabajo: si su ticket tiene un conjunto de reglas que determinan su movimiento entre NUEVO, TRIUNFADO, EN PROGRESO, NECESIDADES-QA, FALLIDO-QA y VERIFICADO (por ejemplo), usted tiene una máquina de estado simple.

Construir sistemas embebidos pequeños y fácilmente comprobables: la señalización del semáforo es un ejemplo clave en el que la lista de todos los estados posibles debe enumerarse y conocerse en su totalidad.

Los parseadores y los lexers se basan en gran medida en las máquinas de estado, ya que la forma en que se determina la transmisión de algo se basa en dónde se encuentra en ese momento.

Answer 7

La mayoría de los flujos de trabajo se pueden implementar como máquinas de estado. Por ejemplo, el procesamiento deja solicitudes u órdenes.

Si está utilizando .NET, pruebe Windows Workflow Foundation. Puede implementar un flujo de trabajo de máquina de estado con bastante rapidez.

Answer 8

Las máquinas de estado están en todas partes. Las máquinas de estado son clave en las interfaces de comunicaciones donde un mensaje necesita ser analizado a medida que se recibe. Además, ha habido muchas veces en el desarrollo de sistemas integrados que he necesitado para separar una tarea en tareas múltiples debido a estrictas restricciones de tiempo.

Answer 9

Las máquinas de estado finito se pueden usar para el análisis morfológico en cualquier lenguaje natural.

Teóricamente, esto significa que la morfología y la sintaxis se dividen entre niveles computacionales, siendo uno el estado finito y el otro moderadamente sensible al contexto (por lo tanto, la necesidad de otros modelos teóricos para explicar palabra por palabra en lugar de relaciones morfema-morfema).

Esto puede ser útil en el área de traducción automática y glosa de palabras. Ostensiblemente, son características de bajo costo para extraer aplicaciones de aprendizaje automático menos triviales en PNL, como el análisis sintáctico o de dependencia.

Si está interesado en obtener más información, puede consultar la Morfología de estados finitos de Beesley y Karttunen, y la Caja de herramientas de estados finitos de Xerox que diseñaron en PARC.

Answer 10

Si está utilizando C #, cada vez que escriba un bloque de iterador le está pidiendo al compilador que cree una máquina de estado para usted (haciendo un seguimiento de dónde se encuentra en el iterador, etc.).

Answer 11

Tengo un ejemplo de un sistema actual en el que estoy trabajando. Estoy en el proceso de construir un sistema de comercio de acciones. El proceso de seguimiento del estado de un pedido puede ser complejo, pero si construye un diagrama de estado para el ciclo de vida de un pedido, hace que la aplicación de nuevas transacciones entrantes al pedido existente sea mucho más simple. Hay muchas menos comparaciones necesarias para aplicar esa transacción si sabe por su estado actual que la nueva transacción solo puede ser una de tres cosas en lugar de una de 20. Hace que el código sea mucho más eficiente.

Answer 12

Un FSM se usa en todos los lugares donde tiene múltiples estados y necesita pasar a un estado diferente en el estímulo.

(resulta que esto abarca la mayoría de los problemas, al menos teóricamente)

Answer 13

Una gran cantidad de diseño de hardware digital implica la creación de máquinas de estado para especificar el comportamiento de sus circuitos. Sale bastante si estás escribiendo VHDL.

Answer 14

Las expresiones regulares son otro ejemplo de cómo entran en juego las máquinas de estados finitos (o "autómatas de estados finitos").

Una expresión regular compilada es una máquina de estados finitos, y los conjuntos de cadenas que las expresiones regulares pueden igualar son exactamente los idiomas que los autómatas de estados finitos pueden aceptar (llamados "lenguajes regulares").

Answer 15

¿Qué tipo de tarea?

Cualquier tarea, pero por lo que he visto, El análisis de cualquier tipo se implementa con frecuencia como una máquina de estado.

¿Por qué?

Analizar una gramática generalmente no es una tarea sencilla. Durante la fase de diseño, es bastante común que se dibuje un diagrama de estado para probar el algoritmo de análisis sintáctico. Traducir eso a una implementación de máquina de estado es una tarea bastante simple.

¿Cómo?

Bueno, estás limitado solo por tu imaginación.

Lo he visto hecho con declaraciones de casos y bucles .

Lo he visto hecho con etiquetas y declaraciones goto

Incluso lo he visto hecho con estructuras de indicadores de función que representan el estado actual. Cuando el estado cambia, uno o más punteros a la función se actualizan.

Lo he visto solo en código, donde un cambio de estado simplemente significa que está ejecutando en una sección diferente de código. (sin variables de estado, y código de redundancia cuando sea necesario. Esto se puede demostrar como un tipo muy simple, que es útil solo para conjuntos muy pequeños de datos.

int a[10] = {some unsorted integers};

not_sorted_state:;
    z = -1;
    while (z < (sizeof(a) / sizeof(a[0]) - 1)
    {
        z = z + 1
        if (a[z] > a[z + 1])
        {
            // ASSERT The array is not in order
            swap(a[z], a[z + 1];        // make the array more sorted
            goto not_sorted_state;      // change state to sort the array
        }
    }
    // ASSERT the array is in order

No hay variables de estado, pero el código en sí mismo representa el estado

Answer 16

Buenas respuestas Aquí están mis 2 centavos. Las máquinas de estados finitos son una idea teórica que puede implementarse de diferentes maneras, como una tabla, o como un cambio de tiempo (pero no le digas a nadie que es una manera de decir "por los horrores" ). Es un teorema que cualquier FSM corresponde a una expresión regular, y viceversa. Como una expresión regular corresponde a un programa estructurado, a veces puede simplemente escribir un programa estructurado para implementar su FSM. Por ejemplo, un analizador simple de números podría escribirse de la siguiente manera:

/* implement dd*[.d*] */
if (isdigit(*p)){
    while(isdigit(*p)) p++;
    if (*p==''.''){
        p++;
        while(isdigit(*p)) p++;
    }
    /* got it! */
}

Entiendes la idea. Y, si hay una forma de que funcione más rápido, no sé qué es.

Answer 17

No vi nada aquí que explicara el motivo por el que los uso.

A efectos prácticos, un programador generalmente tiene que agregar uno cuando se ve obligado a devolver un hilo / salir a la derecha en el medio de una operación.

Por ejemplo, si tiene una solicitud HTTP multi-estado, es posible que tenga un código de servidor que se vea así:

Show form 1
process form 1
show form 2
process form 2

El hecho es que, cada vez que muestra un formulario, debe salir de todo su hilo en el servidor (en la mayoría de los idiomas), incluso si el código fluye lógicamente y utiliza las mismas variables.

El acto de poner un corte en el código y devolver el hilo generalmente se hace con una declaración de interruptor y crea lo que se llama una máquina de estado (Versión muy básica).

A medida que se vuelve más complejo, puede ser realmente difícil averiguar qué estados son válidos. Generalmente, las personas definen una " Tabla de transición del estado " para describir todas las transiciones de estado.

Escribí una biblioteca de máquinas de estado , el concepto principal es que realmente puede implementar su tabla de transición de estado directamente. Fue un ejercicio realmente bueno, no estoy seguro de lo bien que va a pasar, sin embargo ...

Answer 18

Un caso de uso típico son los semáforos.

En una nota de implementación: las enumeraciones de Java 5 pueden tener métodos abstractos, que es una forma excelente de encapsular el comportamiento dependiente del estado.