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 (Mealy) 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". [1]
Definicion formal
Una máquina de Moore se puede definir como una tupla de 6 que consta de lo siguiente:
- Un conjunto finito de estados
- Un estado de inicio (también llamado estado inicial) que es un elemento de
- Un conjunto finito llamado alfabeto de entrada.
- Un conjunto finito llamado alfabeto de salida.
- Una función de transición mapear un estado y el alfabeto de entrada al siguiente estado
- Una función de salida mapeo de cada estado al alfabeto de salida
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. [ aclaración necesaria ]
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 ), a diferencia del estado actual ( como entrada a ). Cuando se representa como un diagrama de estado ,
- 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 Mealy con los mismos estados y transiciones y la función de salida , que toma cada par de entrada de estado y rinde , dónde es función de salida y es función de transición.
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 del estado a estado . La entrada que causa la transición etiqueta el borde . La salida correspondiente a esa entrada, es la etiqueta del estado. [2] Observe 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. Ésta es la definición original de E. Moore. Es un error común usar la etiqueta de estado como salida para la transición .
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 en 1 a partir de entonces cuando al menos dos ceros y dos unos se han producido como entradas.
A la derecha se muestra una máquina 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:
Estado actual | Aporte | Siguiente estado | Producción |
---|---|---|---|
A | 0 | D | 0 |
1 | B | ||
B | 0 | mi | 0 |
1 | C | ||
C | 0 | F | 0 |
1 | C | ||
D | 0 | GRAMO | 0 |
1 | mi | ||
mi | 0 | H | 0 |
1 | F | ||
F | 0 | I | 0 |
1 | F | ||
GRAMO | 0 | GRAMO | 0 |
1 | H | ||
H | 0 | H | 0 |
1 | I | ||
I | 0 | I | 1 |
1 | I |
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", [1] el autómatas (o máquinas) se definen como tener estados, símbolos de entrada y símbolos de salida. Se prueban nueve teoremas sobre la estructura dey experimentos con . Mas tarde, " las máquinas "se conocieron como" máquinas de Moore ".
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:
Dado un arbitrario máquina , de modo que cada dos de sus estados se distingan entre sí, entonces existe un experimento de longitud que determina el estado de al final del experimento.
En 1957, AA Karatsuba demostró los siguientes dos teoremas, 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 un máquina, de modo que cada dos de sus estados se distingan 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.
Teorema B. Existe un 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 .
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. [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
Referencias
- ↑ a b Moore, Edward F (1956). "Experimentos de Gedanken en máquinas secuenciales". Automata Studies, Annals of Mathematical Studies . Princeton, Nueva Jersey: Princeton University Press (34): 129-153.
- ^ 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 .
- ^ Karatsuba, AA (1960). "Solución de un problema a partir de la teoría de los autómatas finitos". Uspekhi Mat. 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 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