Máquina de Mealy y de Moore

Máquinas Secuencial de Mealy
Máquinas Secuencial de Moore
Autómata Finito Determinista

UTN-FRC-SSL-Ing.Lic. Julio Castillo-

Def:
Es un modelo matemático teórico en el que se
formaliza uncomputador abstracto en un
paradigma de tiempo discreto.
Características:
- son máquinas traductoras
- operan indefinidamente
Antecedentes:
- Máquina de Mealy (George Mealy, 1955)
- Máquina deMoore (Edward Moore,1956)
- Máquina RAM (Shepherdson & Sturgis,1963;
Minsky,1961)
UTN-FRC-SSL-Ing.Lic. Julio Castillo-

ME = (ΣE, ΣS, Q, f, g)
Donde:
- ΣE : Alfabeto de símbolos de entrada
-ΣS : Alfabeto de símbolos de salida
- Q : Conjunto finito, no vacío, de estados
posibles.
- f : Función de transición, f: Q x ΣE Q
- g : Función de salida,
g: Q x ΣE ΣS

UTN-FRC-SSL-Ing.Lic.Julio Castillo-

Sea M = ({a,b,c}, {d,e,f}, {p,q,r,s}, f, g)
Con f: Q x ΣE
Q y g: Q x ΣE
ΣS :

O su representación
Equivalente:

UTN-FRC-SSL-Ing.Lic. Julio Castillo-

Es una máquinasecuencial
Es una máquina traductora
Tiene estados, entradas y salidas
En este ejemplo partiendo del estado p la
cadena α=acbbc se traduce como α’=dfeee.

UTN-FRC-SSL-Ing.Lic. Julio Castillo-Deducir la Máquina de Mealy representado
por el siguiente grafo:

UTN-FRC-SSL-Ing.Lic. Julio Castillo-

- Propuesta por (Edward Moore, 1956):
MO = (ΣE, ΣS, Q, f, g)
Con: f: Q x ΣE
Q y g: Q

ΣS-Notar que la función de salida depende
únicamente del estado actual.
- Incorpora un retardo entre la entrada y salida:
Ya que st = g(qt), y qt = f(qt-1,et-1), se tiene que
st = g(f(qt-1,et-1)).- Se puede demostrar que existe una equivalencia
con las Máquinas de Mealy.

UTN-FRC-SSL-Ing.Lic. Julio Castillo-

Son máquinas secuenciales
Presentan 1 estado Inicial
Presentan 1 o másestados finales
Tienen un conjunto finito de estados
Leen/Escriben en una cinta
Características:
- Reconocedores de lenguajes
- Traductores

UTN-FRC-SSL-Ing.Lic. Julio Castillo-

Autómata...