Maquinas
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...
Regístrate para leer el documento completo.