Diferencia entre Mealy y Moore

Question

¿Tiene alguna importancia real la diferencia entre las máquinas de estado Mealy y Moore cuando se trata de una implementación de C? ¿Cuál sería esa diferencia normalmente?

Hace mucho tiempo, era mucho más fácil para mí entender las ventajas/desventajas de Mealy/Moore cuando se trata de RTL. La salida completa dependiendo del estado actual/salida dependiendo del estado actual + diferencia de entrada actual tiene sentido, al igual que el hecho de que Mealy podría hacerse con 1 estado menos en algunos casos también tenía sentido. Asociar diagramas de tiempo con cada implementación de FSM también hizo la diferencia entre ellos más clara.

Digamos que estoy haciendo una máquina de estados en C. En un caso, un LUT depende de las entradas de estado/corriente (Mealy) y en el Moore el LUT solo busca el estado actual y devuelve el siguiente. En cualquiera de los resultados ocurre después del regreso de la LUT (creo, aunque podría estar equivocado). No he pensado en una manera clara de que un Mealy tenga una ventaja cuando está codificado en C. Temas como la legibilidad del código, la velocidad, la densidad del código, la facilidad de diseño pueden ser temas relevantes. Desde mi punto de vista, los dos modelos parecen casi iguales.

Quizás esta diferencia sea solo un tema para los académicos, y en la práctica en las implementaciones C la diferencia es insignificante. Si conoce las formas clave en que una implementación de máquina en estado C diferiría entre Mealy y Moore, y si hay ventajas reales (que también son significativas) me gustaría saber. Me gustaría enfatizar que no estoy preguntando por las implementaciones de RTL.

vi otro puesto Mealy/Moore aquí: Mealy v/s. Moore

Pero esto no es realmente el nivel de explicación que estoy buscando.

Answer 1

Tiene un procedimiento mecánico para convertir un formalismo en otro, por lo que no hay diferencia estructural entre los dos.

Hablando de las diferencias en la implementación, los dos formalismos solo difieren en la función de salida, que le indica qué símbolo se debe mostrar. Específicamente:

1. En una máquina de Moore, la salida depende sólo del estado actual
2. En una máquina Mealy, la salida depende del estado actual y la entrada actual.

una máquina Moore puede ser un poco más fácil de implementar porque tiene menos información para rastrear cuando se trata de generar la salida, pero la diferencia será realmente pequeña.

Aquí es cómo una simple máquina de Moore se vería en C:

int state = INITIAL; 
while (!isTerminal(state)) { 
    char input = nextInputSymbol(); 
    fprintf(output, "%c", nextOutputSymbol(state)); 
    state = nextState(state, input); 
} 

y aquí está la máquina Mealy:

int state = INITIAL; 
while (!isTerminal(state)) { 
    char input = nextInputSymbol(); 
    fprintf(output, "%c", nextOutputSymbol(input, state)); 
    state = nextState(state, input); 
} 

como se ve, la única diferencia está en la definición de nextOutputSymbol(). Si la implementación de dicha función es más fácil para uno u otro formalismo, realmente depende de la aplicación específica.

nextInputSymbol es sólo una rutina para obtener un nuevo símbolo (que podría ser un scanf o similares) y nextState dependerá de la máquina específica, pero su complejidad no va a cambiar mucho entre Mealy y Moore equivalente.

En particular, tanto nextOutputSymbol y nextState se reducen a una búsqueda en la tabla o una switch o una cadena if/else, sin la dificultad de implementación real. Son realmente aburridos de escribir, de verdad.

NOTA: He omitido la comprobación de errores en los fragmentos de código para mantenernos enfocados en el punto principal de la discusión. El código de mundo real realizaría algunas comprobaciones adicionales, como el manejo de EOF en nextInputSymbol o break en estados de error.

Answer 2

Moore Machine: La salida solo depende del estado actual. Mealy Machine: La salida depende de la entrada actual del presente estado &.