Maquinas

Máquinas de Moore
Una máquina de Moore es similar a una de Mealy, salvo en que la respuesta sólo depende del estado actual de la máquina y es independiente de la entrada. Precisamente, una máquinade Moore es una estructura de la forma 

donde 

La semántica procedimental de la máquina de Moore es la siguiente:
Al inicio de cualquier computación, la máquina se encuentra en el estado q0.Posteriormente, cuando la máquina se encuentra en un estado , y recibe una literal de entrada , entonces transita al nuevo estado  y emite el símbolo de salida .
Ejemplos 1. Congruencias módulo3: Supongamos que se da un número  en su representación binaria y se quiere calcular su residuo módulo 3. Consideremos la máquina cuya representación gráfica se muestra en la figura (3.3). 
  
Figure3.3: Máquina de Moore para calcular congruencias módulo 3 de números dados en binario. |
|

Las funciones de transición y de respuesta quedan especificadas de manera tabular como sigue: 

Por inducciónen la longitud n de cualquier palabra , que sea la representación en binario de un número  se puede ver que la respuesta final obtenida al aplicar  es . En efecto, para n=1, con las palabras '0' y'1' se tiene las respuestas correctas 0 y 1. Sea n>0. Supongamos que para una palabra , de longitud n-1, se tiene como respuesta final i, donde  y x es el número representado en binario por .Para  el número representado por la concatenación de  con s,  es 2x+s, el cual es congruente módulo 3 con . Al tabular estos últimos valores se tiene 

lo que corresponde naturalmente a la tabla detransiciones del autómata construído. De hecho, éste es un caso particular del siguiente ejemplo más general: Sea n>1 una base de representación de números naturales y sea k>0 un número natural. Sea  lamáquina de Moore tal que
* posee n símbolos de entrada ,
* posee k estados , y k símbolos de salida, uno por cada estado.
* tiene como transición a la función , y
* tiene como...