Estoy buscando buenos ejemplos de máquinas de estados finitos; el lenguaje no es particularmente importante, solo buenos ejemplos.

Las implementaciones de código son útiles (pseudocódigo generalizado), pero también es muy útil para reunir los diversos usos de los FSM.

Los ejemplos no necesariamente tienen que estar basados ​​en computadora, por ejemplo, el ejemplo de Mike Dunlavey Railroad networks es muy útil.

A Safe (evento activado)

• Estados : múltiples estados "bloqueados", un estado "desbloqueado"
• Transiciones : las combinaciones / teclas correctas lo mueven de los estados bloqueados iniciales a los estados bloqueados más cerca de desbloqueado, hasta que finalmente lo desbloquea. Las combinaciones / teclas incorrectas lo devuelven al estado bloqueado inicial (a veces conocido como inactivo .

Semáforo (tiempo activado | sensor [evento] activado)

• Estados : ROJO, AMARILLO, VERDE (ejemplo más simple)
• Transiciones : después de un temporizador, cambie ROJO a VERDE, VERDE a AMARILLO y AMARILLO a ROJO. También podría activarse al detectar automóviles en varios estados (más complicados).

Máquina expendedora (evento activado, una variación de la caja fuerte )

• Estados : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS, etc., VEND, CHANGE
• Transiciones : Cambios de estado al insertar monedas, billetes, transición a VEND a la cantidad correcta de compra (o más), luego transición a CAMBIO o INACTIVO (dependiendo de cuán ética sea su máquina expendedora)

Ejemplo de protocolo de puerta de enlace fronterizo

BGP es un protocolo que respalda las decisiones básicas de enrutamiento en Internet. Mantiene una tabla para determinar la accesibilidad de los hosts desde un nodo determinado e hizo que Internet sea realmente descentralizada.

En la red, cada nodo BGP es un par y utiliza una máquina de estados finitos, con uno de los seis estados Idle , Connect , Active , OpenSent , OpenConfirm y establecida . Cada conexión de igual en la red mantiene uno de estos estados.

El protocolo BGP determina los mensajes que se envían a sus pares para cambiar su estado.

BPG statechart.

Ocioso

El primer estado de inactividad . En este estado, BGP inicializa los recursos, rechaza los intentos de conexión entrantes e inicia una conexión con el igual.

Conectar

El segundo estado Conecta . En este estado, el enrutador espera a que se complete la conexión y pasa al estado OpenSent si tiene éxito. Si no tiene éxito, restablece el temporizador ConnectRetry y pasa al estado Activo al expirar.

Activo

En el estado Activo , el enrutador restablece el temporizador ConnectRetry a cero y vuelve al estado Conectar .

OpenSent

En el estado OpenSent , el enrutador envía un mensaje Open y espera a cambio uno. Los mensajes de Keepalive se intercambian y, una vez recibidos con éxito, el enrutador se coloca en el estado establecido .

Establecido

En el estado establecido , el enrutador puede enviar / recibir: Keepalive; Actualizar; y mensajes de notificación a / de su par.

Más información sobre BGP está en wikipedia

Son útiles para modelar todo tipo de cosas. Por ejemplo, un ciclo electoral puede ser modelado con estados a lo largo de las líneas de (gobierno normal) - elección llamada -> (campaña temprana) - Parlamento disuelto -> (campaña fuerte) - elección -> (conteo de votos ) Luego, ya sea (recuento de votos) --no mayoría -> (negociaciones de coalición) - acuerdo alcanzado -> (gobierno normal) o (recuento de votos) - mayoría -> (gobierno normal). He implementado una variante de este esquema en un juego con un subjuego político.

También se usan en otros aspectos de los juegos: la IA a menudo se basa en el estado; Las transiciones entre menús y niveles, y las transiciones al morir o el nivel completado a menudo están bien modeladas por los FSM.

El analizador CSV utilizado en el complemento jquery-csv

Es un analizador de gramática básico de Chomsky Tipo III .

Un tokenizer regex se utiliza para evaluar los datos en una base de char-by-char. Cuando se encuentra un control char, el código se pasa a una instrucción switch para una evaluación adicional basada en el estado inicial. Los caracteres sin control se agrupan y copian en masa para reducir el número de operaciones de copia de cadena necesarias.

El tokenizador:

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

El primer conjunto de coincidencias son los caracteres de control: delimitador de valor (") separador de valor (,) y separador de entrada (todas las variaciones de nueva línea). La última coincidencia maneja la agrupación de caracteres sin control.

Hay 10 reglas que el analizador debe cumplir:

• Regla # 1 - Una entrada por línea, cada línea termina con una nueva línea
• Regla n. ° 2: se omite la nueva línea final al final del archivo
• Regla n. ° 3: la primera fila contiene datos de encabezado
• Regla n. ° 4: los espacios se consideran datos y las entradas no deben contener una coma final
• Regla # 5 - Las líneas pueden o no estar delimitadas por comillas dobles
• Regla n. ° 6: los campos que contienen saltos de línea, comillas dobles y comas deben ir entre comillas dobles
• Regla n. ° 7: si se utilizan comillas dobles para encerrar los campos, se debe escapar una comilla doble que aparezca dentro de un campo precediéndola con otra comilla doble
• Enmienda n. ° 1: un campo sin comillas puede o puede
• Enmienda # 2 - Un campo citado puede o no
• Enmienda # 3 - El último campo en una entrada puede o no contener un valor nulo

Nota: Las 7 reglas principales se derivan directamente de IETF RFC 4180 . Los últimos 3 se agregaron para cubrir casos extremos introducidos por aplicaciones modernas de hoja de cálculo (ex Excel, hoja de cálculo de Google) que no delimitan (es decir, cotizan) todos los valores de forma predeterminada. Intenté contribuir con los cambios al RFC pero aún no he escuchado una respuesta a mi consulta.

Suficiente con la liquidación, aquí está el diagrama:

Estados:

1. estado inicial para una entrada y / o un valor
2. se ha encontrado una cita de apertura
3. se ha encontrado una segunda cita
4. se ha encontrado un valor sin comillas

Transiciones:

• a. comprueba los valores entre comillas (1), los valores sin comillas (3), los valores nulos (0), las entradas nulas (0) y las nuevas entradas (0)
• si. busca una segunda cotización char (2)
• do. comprueba una cita escapada (1), fin de valor (0) y fin de entrada (0)
• re. comprueba el final del valor (0) y el final de la entrada (0)

Nota: en realidad le falta un estado. Debe haber una línea desde 'c' -> 'b' marcada con el estado '1' porque un segundo delimitador escapado significa que el primer delimitador aún está abierto. De hecho, probablemente sería mejor representarlo como otra transición. Crear estos es un arte, no hay una única forma correcta.

Nota: También le falta un estado de salida, pero en los datos válidos el analizador siempre termina en la transición 'a' y ninguno de los estados es posible porque no queda nada para analizar.

La diferencia entre estados y transiciones:

Un estado es finito, lo que significa que solo se puede inferir que significa una cosa.

Una transición representa el flujo entre estados, por lo que puede significar muchas cosas.

Básicamente, la relación estado-> transición es 1 -> * (es decir, uno a muchos). El estado define "qué es" y la transición define "cómo se maneja".

Nota: No se preocupe si la aplicación de estados / transiciones no se siente intuitiva, no es intuitiva. Se necesitó una correspondencia extensa con alguien mucho más inteligente que yo antes de que finalmente pudiera mantener el concepto.

El seudocódigo:

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
  }
}

Nota: Esta es la esencia, en la práctica hay mucho más que considerar. Por ejemplo, comprobación de errores, valores nulos, una línea en blanco al final (es decir, que es válida), etc.

En este caso, el estado es la condición de las cosas cuando el bloque de coincidencia de expresiones regulares finaliza una iteración. La transición se representa como las declaraciones de caso.

Como humanos, tenemos una tendencia a simplificar las operaciones de bajo nivel en resúmenes de alto nivel, pero trabajar con un FSM es trabajar con operaciones de bajo nivel. Si bien los estados y las transiciones son muy fáciles de trabajar individualmente, es inherentemente difícil visualizar todo de una vez. Me resultó más fácil seguir los caminos individuales de ejecución una y otra vez hasta que pude intuir cómo se desarrollan las transiciones. Es como aprender matemática básica, no podrás evaluar el código desde un nivel superior hasta que los detalles de nivel bajo comiencen a ser automáticos.

Aparte: si observa la implementación real, faltan muchos detalles. Primero, todos los caminos imposibles arrojarán excepciones específicas. Debería ser imposible golpearlos, pero si algo se rompe, desencadenarán excepciones en el corredor de prueba. En segundo lugar, las reglas del analizador de lo que está permitido en una cadena de datos CSV 'legal' son bastante flexibles, por lo que el código necesario para manejar una gran cantidad de casos específicos. Independientemente de ese hecho, este fue el proceso utilizado para burlarse del FSM antes de todas las correcciones de errores, extensiones y ajustes.

Como con la mayoría de los diseños, no es una representación exacta de la implementación, pero describe las partes importantes. En la práctica, en realidad hay 3 funciones de analizador diferentes derivadas de este diseño: un divisor de línea específico de csv, un analizador de una sola línea y un analizador de varias líneas completo. Todos operan de manera similar, difieren en la forma en que manejan los caracteres de nueva línea.

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;      
  }

} 

Ahí tienes. OK, no es brillante, pero muestra la idea.

A menudo encontrará FSM en productos de telecomunicaciones porque ofrecen una solución simple a una situación compleja.

He descubierto que pensar / modelar un ascensor (elevador) es un buen ejemplo de una máquina de estados finitos. Requiere poco en el camino de introducción, pero proporciona una situación lejos de trivial para implementar.

Los estados son, por ejemplo, en la planta baja, en el primer piso, etc., y se mueven de la tierra al primer piso, o se mueven de la tercera a la planta baja, pero actualmente se encuentran entre los pisos 3 y 2, y así sucesivamente.

El efecto de los botones en la jaula del elevador y en los mismos pisos proporciona entradas, cuyo efecto depende tanto del botón que se presiona junto con el estado actual.

Cada piso, excepto la parte superior e inferior, tendrá dos botones: uno para solicitar que el elevador suba, el otro para bajar.

OK, aquí hay un ejemplo. Suponga que desea analizar un número entero. Sería algo así como dd*donde des un dígito entero.

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

Por supuesto, como dijo @Gary, podría disfrazar esos gotos mediante una declaración de cambio y una variable de estado. Tenga en cuenta que se puede estructurar a este código, que es isomorfo a la expresión regular original:

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

Por supuesto, también puedes hacerlo con una tabla de búsqueda.

Las máquinas de estados finitos pueden hacerse de muchas maneras, y muchas cosas pueden describirse como instancias de máquinas de estados finitos. No es tanto una "cosa" como un concepto, para pensar sobre las cosas.

Ejemplo de red ferroviaria

Un ejemplo de un FSM es una red ferroviaria.

Hay un número finito de interruptores donde un tren puede ir a una de las dos vías.

Hay un número finito de pistas que conectan estos interruptores.

En cualquier momento, un tren está en una vía, se puede enviar a otra vía cruzando un interruptor, basado en un solo bit de información de entrada.

Máquina de estado finito en rubí:

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

Ese es el comportamiento de un solo nodo de cómputo en un sistema distribuido, configurando un esquema de comunicación basado en enlaces. Más o menos. En forma gráfica se parece a esto:

Consulte este enlace para ver algunos ejemplos simples de análisis léxico (FSM):

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

También puede consultar el "libro del dragón" para ver ejemplos (no es una lectura ligera)

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

En la práctica, las máquinas de estado a menudo se usan para:

• Propósitos de diseño (modelar las diferentes acciones en un programa)
• Analizadores de lenguaje natural (gramática)
• Análisis de cadenas

Un ejemplo sería una máquina de estado que escanea una cadena para ver si tiene la sintaxis correcta. Los códigos postales holandeses, por ejemplo, están formateados como "1234 AB". La primera parte solo puede contener números, la segunda solo letras. Se podría escribir una máquina de estado que haga un seguimiento de si está en el estado NÚMERO o en el estado LETRA y, si encuentra una entrada incorrecta, rechazarla.

Esta máquina de estados aceptadores tiene dos estados: numérico y alfa. La máquina de estados comienza en el estado numérico y comienza a leer los caracteres de la cadena para verificar. Si se encuentran caracteres inválidos durante cualquiera de los estados, la función regresa con un valor Falso, rechazando la entrada como inválida.

Código de 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)

Fuente: Máquinas de estado (finito) en la práctica