Máquina de Moore - Moore machine

En la teoría de la computación , una máquina de Moore es una máquina de estados finitos cuyos valores de salida están determinados solo por su estado actual . Esto contrasta con una máquina Mealy , cuyos valores de salida están determinados tanto por su estado actual como por los valores de sus entradas. La máquina Moore lleva el nombre de Edward F. Moore , quien presentó el concepto en un artículo de 1956, " Experimentos de Gedanken sobre máquinas secuenciales".

Definicion formal

Una máquina de Moore se puede definir como una tupla de 6 que consta de lo siguiente: ${\ Displaystyle (Q, q_ {0}, \ Sigma, O, \ delta, G)}$

• Un conjunto finito de estados ${\ displaystyle Q}$
• Un estado de inicio (también llamado estado inicial) que es un elemento de${\ Displaystyle q_ {0}}$${\ displaystyle Q}$
• Un conjunto finito llamado alfabeto de entrada. ${\ Displaystyle \ Sigma}$
• Un conjunto finito llamado alfabeto de salida. ${\ Displaystyle O}$
• Una función de transición que mapea un estado y el alfabeto de entrada al siguiente estado.${\ Displaystyle \ delta: Q \ times \ Sigma \ rightarrow Q}$
• Una función de salida que asigna cada estado al alfabeto de salida.${\ displaystyle G: Q \ rightarrow O}$

Una máquina de Moore puede considerarse como un tipo restringido de transductor de estado finito .

Representación visual

Mesa

La tabla de transición de estado es una tabla que muestra la relación entre una entrada y un estado.

Diagrama

El diagrama de estado de una máquina de Moore o el diagrama de Moore es un diagrama que asocia un valor de salida con cada estado. La máquina de Moore es un productor de salida.

Relación con las máquinas Mealy

Como las máquinas de Moore y Mealy son tipos de máquinas de estados finitos, son igualmente expresivas: cualquiera de los dos tipos se puede utilizar para analizar un lenguaje regular .

La diferencia entre las máquinas Moore y las máquinas Mealy es que en las últimas, la salida de una transición está determinada por la combinación del estado actual y la entrada actual ( como entrada a ), en oposición al estado actual ( como entrada a ). . Cuando se representa como un diagrama de estado , ${\ Displaystyle S \ times \ Sigma}$${\ Displaystyle G}$${\ Displaystyle S}$${\ Displaystyle G}$

• para una máquina de Moore, cada nodo (estado) está etiquetado con un valor de salida;
• para una máquina Mealy, cada arco (transición) está etiquetado con un valor de salida.

Cada máquina Moore es equivalente a la máquina Mealy con los mismos estados y transiciones y la función de salida , que toma cada par estado-entrada y produce , donde es la función de salida y la función de transición de is . ${\ Displaystyle M}$${\ Displaystyle G (s, \ sigma) \ rightarrow G_ {M} (\ delta _ {M} (s, \ sigma))}$${\ Displaystyle (s, \ sigma)}$${\ Displaystyle G_ {M} (\ delta _ {M} (s, \ sigma))}$${\ Displaystyle G_ {M}}$${\ Displaystyle M}$${\ Displaystyle \ delta _ {M}}$${\ Displaystyle M}$

Sin embargo, no todas las máquinas Mealy se pueden convertir en una máquina Moore equivalente. Algunos pueden convertirse solo en una máquina Moore casi equivalente, con salidas desplazadas en el tiempo. Esto se debe a la forma en que las etiquetas de estado se emparejan con las etiquetas de transición para formar los pares de entrada / salida. Considere una transición de un estado a otro . La entrada que causa la transición etiqueta el borde . La salida correspondiente a esa entrada es la etiqueta de estado . Tenga en cuenta que este es el estado de origen de la transición. Entonces, para cada entrada, la salida ya está fija antes de que se reciba la entrada y depende únicamente del estado actual. Esta es la definición original de E. Moore. Es un error común usar la etiqueta de estado como salida para la transición . ${\ Displaystyle s_ {i} \ rightarrow s_ {j}}$${\ Displaystyle s_ {i}}$${\ Displaystyle s_ {j}}$${\ Displaystyle s_ {i} \ rightarrow s_ {j}}$${\ Displaystyle (s_ {i}, s_ {j})}$${\ Displaystyle s_ {i}}$${\ Displaystyle s_ {j}}$${\ Displaystyle s_ {i} \ rightarrow s_ {j}}$

Ejemplos de

Tipos según número de entradas / salidas.

Sencillo

Las máquinas Moore simples tienen una entrada y una salida:

• detector de bordes con XOR
• máquina sumadora binaria
• sistemas secuenciales sincronizados (una forma restringida de la máquina de Moore donde el estado cambia solo cuando cambia la señal del reloj global)

La mayoría de los sistemas electrónicos digitales están diseñados como sistemas secuenciales sincronizados . Los sistemas secuenciales con reloj son una forma restringida de máquina de Moore donde el estado cambia solo cuando cambia la señal del reloj global. Normalmente, el estado actual se almacena en flip-flops y se conecta una señal de reloj global a la entrada de "reloj" de los flip-flops. Los sistemas secuenciales sincronizados son una forma de resolver problemas de metaestabilidad . Una máquina Moore electrónica típica incluye una cadena lógica combinacional para decodificar el estado actual en las salidas (lambda). En el instante en que cambia el estado actual, esos cambios se propagan a través de esa cadena y casi instantáneamente se actualiza la salida. Existen técnicas de diseño para garantizar que no se produzcan fallos en las salidas durante ese breve período mientras esos cambios se propagan por la cadena, pero la mayoría de los sistemas están diseñados para que los fallos durante ese breve tiempo de transición se ignoren o sean irrelevantes. Luego, las salidas permanecen iguales indefinidamente (los LED permanecen brillantes, la energía permanece conectada a los motores, los solenoides permanecen energizados, etc.), hasta que la máquina Moore cambia de estado nuevamente.

Ejemplo resuelto

Una red secuencial tiene una entrada y una salida. La salida se convierte en 1 y permanece como 1 a partir de entonces cuando al menos dos ceros y dos unos se han producido como entradas.

Ejemplo de máquina moore

A la derecha se muestra una máquina de Moore con nueve estados para la descripción anterior. El estado inicial es el estado A y el estado final es el estado I. La tabla de estados para este ejemplo es la siguiente:

Complejo

Las máquinas Moore más complejas pueden tener múltiples entradas y múltiples salidas.

Experimentos-gedanken

En el artículo de Moore " Gedanken-experiment on Sequential Machines", los autómatas (o máquinas) se definen por tener estados, símbolos de entrada y símbolos de salida. Se prueban nueve teoremas sobre la estructura y experimentos con . Más tarde, las " máquinas" se conocieron como "máquinas de Moore". ${\ Displaystyle (n; m; p)}$${\ Displaystyle S}$${\ Displaystyle n}$${\ Displaystyle m}$${\ Displaystyle p}$${\ Displaystyle S}$${\ Displaystyle S}$${\ Displaystyle S}$

Al final del artículo, en la sección "Otros problemas", se indica la siguiente tarea:

Otro problema que sigue directamente es la mejora de los límites dados en los teoremas 8 y 9.

El teorema 8 de Moore se formula como:

Dada una máquina arbitraria , tal que cada dos de sus estados se distinguen entre sí, existe un experimento de longitud que determina el estado de al final del experimento.${\ Displaystyle (n; m; p)}$${\ Displaystyle S}$${\ Displaystyle {\ tfrac {n (n-1)} {2}}}$${\ Displaystyle S}$

En 1957, AA Karatsuba demostró los dos teoremas siguientes, que resolvieron completamente el problema de Moore sobre la mejora de los límites de la longitud del experimento de su "Teorema 8".

Teorema A. Si es una máquina, de modo que cada dos de sus estados son distinguibles entre sí, entonces existe un experimento ramificado de longitud como máximo a través del cual se puede determinar el estado de al final del experimento.${\ Displaystyle S}$${\ Displaystyle (n; m; p)}$${\ Displaystyle {\ tfrac {(n-1) (n-2)} {2}} + 1}$${\ Displaystyle S}$

Teorema B. Existe una máquina, cada dos estados de los cuales se distinguen entre sí, de modo que la duración de los experimentos más cortos que establecen el estado de la máquina al final del experimento es igual a .${\ Displaystyle (n; m; p)}$${\ Displaystyle {\ tfrac {(n-1) (n-2)} {2}} + 1}$

Los teoremas A y B se utilizaron para la base del trabajo de curso de un estudiante de cuarto año, AA Karatsuba, "Sobre un problema de la teoría de autómatas", que se distinguió por referencia testimonial en el concurso de trabajos de estudiantes de la facultad de mecánica y matemáticas de la Universidad Estatal de Moscú Lomonosow en 1958. El artículo de Karatsuba fue entregado a la revista Uspekhi Mat. Nauk el 17 de diciembre de 1958 y se publicó allí en junio de 1960.

Hasta el día de hoy (2011), el resultado de Karatsuba sobre la duración de los experimentos es el único resultado no lineal exacto, tanto en la teoría de autómatas como en problemas similares de la teoría de la complejidad computacional.

Ver también

• Circuito sincrónico
• Máquina harinosa
• Máquina de estado algorítmica
• Sistema autónomo (matemáticas)

Referencias

Otras lecturas

• Conway, JH (1971). Álgebra regular y máquinas finitas . Londres: Chapman y Hall. ISBN 0-412-10620-5. Zbl  0231.94041 .
• Moore EF Gedanken-experimentos sobre máquinas secuenciales. Automata Studies, Annals of Mathematical Studies, 34, 129-153. Prensa de la Universidad de Princeton, Princeton, Nueva Jersey (1956).
• Karatsuba AA Solución de un problema de la teoría de los autómatas finitos. Usp. Estera. Nauk, 15: 3, 157-159 (1960).
• Karatsuba AA Experimente mit Automaten (alemán) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975).
• Karatsuba AA Lista de trabajos de investigación .

Moore-y-Mealy-Machine

enlaces externos

• Medios relacionados con la máquina de Moore en Wikimedia Commons