maquina moore

Máquina de estados finitos cuyos valores de salida están determinados únicamente por su estado actual

En la teoría de la computación , una máquina de Moore es una máquina de estados finitos cuyos valores de salida actuales están determinados únicamente 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. Al igual que otras máquinas de estados finitos, en las máquinas de Moore, la entrada normalmente influye en el siguiente estado. Por lo tanto, la entrada puede influir indirectamente en las salidas posteriores, pero no en la producción actual o inmediata. La máquina de Moore lleva el nombre de Edward F. Moore , quien presentó el concepto en un artículo de 1956, " Gedanken-experiments on Sequential Machines". ^[1]

Definicion formal

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

• Un conjunto finito de estados. ${\displaystyle S}$
• Un estado inicial (también llamado estado inicial) que es un elemento de ${\displaystyle s_{0}}$ ${\displaystyle S}$
• 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 asigna un estado y el alfabeto de entrada al siguiente estado ${\displaystyle \delta :S\times \Sigma \rightarrow S}$
• Una función de salida que asigna cada estado al alfabeto de salida. ${\displaystyle G:S\rightarrow O}$

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

Representación visual

Mesa

Una tabla de transición de estado es una tabla que enumera todos los tripletes en la relación de transición . ${\displaystyle \delta :S\times \Sigma \rightarrow S}$

Diagrama

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

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 tipos puede usarse para analizar un lenguaje regular .

La diferencia entre las máquinas de Moore y las máquinas de Mealy es que en estas últimas, la salida de una transición está determinada por la combinación del estado actual y la entrada actual ( como el dominio de ), en lugar de solo el estado actual ( como el dominio de ) . 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 de Moore es equivalente a la máquina de 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 es la función de transición. ${\displaystyle M}$ ${\displaystyle G(s,\sigma )=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. Algunas sólo pueden convertirse en una máquina Moore casi equivalente, con resultados desplazados en el tiempo. Esto se debe a la forma en que las etiquetas de estado se combinan con las etiquetas de transición para formar los pares de entrada/salida. Consideremos 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 . ^[2] Observe que este es el estado fuente de la transición. Entonces, para cada entrada, la salida ya está fijada antes de recibir la entrada y depende únicamente del estado actual. Ésta es la definición original de E. Moore. Es un error común utilizar 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

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

Simple

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

• detector de bordes usando XOR
• máquina sumadora binaria
• sistemas secuenciales sincronizados (una forma restringida de 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 cronometrados . Los sistemas secuenciales sincronizados son una forma restringida de máquina de Moore donde el estado cambia sólo 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 cronometrados 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 la salida se actualiza. Existen técnicas de diseño para garantizar que no se produzcan fallos en los resultados durante ese breve período mientras esos cambios se propagan a lo largo de 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.

Máquina de Moore en lógica combinacional

Ejemplo resuelto

Una red secuencial tiene una entrada y una salida. La salida se convierte en 1 y permanece 1 a partir de entonces cuando se han producido al menos dos ceros y dos unos 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 de 1956 " Gedanken-experiments on Sequential Machines", ^[1] se define que los autómatas (o máquinas) tienen estados, símbolos de entrada y símbolos de salida. Se demuestran nueve teoremas sobre la estructura y experimentos con . Más tarde, las " máquinas" pasaron a ser conocidas 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 establece la siguiente tarea:

Otro problema inmediatamente siguiente 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 sean distinguibles entre sí, entonces 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 duración del experimento de su "Teorema 8".

Teorema A. Si es una máquina tal que cada dos de sus estados son distinguibles entre sí, entonces existe un experimento ramificado de longitud máxima a través del cual se puede determinar el estado 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 sirvieron de base para el trabajo de curso de un estudiante de cuarto año, AA Karatsuba, "Sobre un problema de la teoría de los autómatas", que se distinguió como referencia testimonial en el concurso de trabajos de estudiantes de la facultad de Mecánica y Matemáticas de la Universidad Estatal de Moscú 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. ^[3]

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 síncrono
• maquina harinosa
• Máquina de estados algorítmica
• Sistema autónomo (matemáticas)

Referencias

1. Moore, Edward F (1956). "Experimentos Gedanken en máquinas secuenciales". Estudios de autómatas, Anales de estudios matemáticos . Princeton, Nueva Jersey: Princeton University Press (34): 129–153.
2. Lee, Edward Ashford; Seshia, Sanjit Arunkumar (2013). Introducción a los sistemas integrados (1.08 ed.). UC Berkeley: Lulu.com. ISBN 9780557708574. Consultado el 1 de julio de 2014 .
3. Karatsuba, AA (1960). "Solución de un problema de la teoría de autómatas finitos". Estera Uspekhi. Nauk (15:3): 157–159.

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 con máquinas secuenciales. Estudios de autómatas, Anales de estudios matemáticos, 34, 129-153. Princeton University Press, Princeton, Nueva Jersey (1956).
• Karatsuba AA Solución de un problema de la teoría de autómatas finitos. Usp. Estera. Nauk, 15:3, 157–159 (1960).
• Karatsuba AA Experimente mit Automaten (alemán) Elektron. Informaciónverarb. Kybernetik, 11, 611–612 (1975).
• Karatsuba AA Lista de trabajos de investigación .

Máquina-de-Moore-y-Mealy

enlaces externos

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