Teoría de la Computación

Teoría de la Computación
tema 2
Prof. Hilda Y. Contreras
Departamento de Computación
hyelitza@ula.ve
http://webdelprofesor.ula.ve/ingenieria/hyelitza

Contenido
Autómatas con salidas yaplicaciones:
• Máquina de Moore
• Máquina de Mealy
• Ejemplos de aplicación

¿Porqué con Salidas?
• Autómatas finitos (Determinista, No
Determinista y con transiciones nulas)
Problemas dedecisión
• Otros autómatas
otros problemas
• Ejemplos de problemas:
– Cálculo matemático
– Transformación, traducción
– Contador, etc.

AF sin salida
Un AF M esta definido como:
M = (Q, Σ, q0, δ,F)
• Q es el conjunto de estados
• Σ es el alfabeto del lenguaje
• q0 es el estado inicial
• δ es la función de transición
• F es el conjunto de estados de
aceptación.

AF con salida
Un AF Scon salida esta definido como:

S = (Q, Σ, Γ, q0, δ, ω)
• Q es el conjunto de estados
• Σ es el alfabeto del lenguaje

• Γ es el alfabeto de salida
• q0 es el estado inicial
• δ es la funciónde transición
• ω es la función de salida (estado o transición)

AF con salida
• Dados Σ = {a,b} y Γ = {y,z}
Moore:
ω:Q

Γ

Mealy:
ω:QxΣ

Γ

Máquina de Moore
Salida – Estado ω : QΓ

• El nombre “Máquina de Moore” viene de su
promotor: Edward F. Moore, pionero en el
estudios de Autómatas, 1956.
• La mayoría de los componentes electrónicos
están diseñadas como sistemassecuenciales
síncronos (forma restringida de máquinas de
Moore)
• p.e. Un Autómata para calcular el residuo de la
división por 3 de un número binario, máquina
expendedora de café, etc.

Máquinade Moore
Si m se divide entre 3 y su resultado es x y
su residuo es p, entonces x * 3 + p = m
Decimal Binario Decimal
Posibles valores de p
de m
de m
de p
0
1
2
3
4
5
6
7

0
1
1011
100
101
110
111

0
1
2
0
1
2
0
1

Γ = {0,1,2}

Máquina de Moore
Entrada w = 1010
Salida s = 01221
|s| = |w| + 1
δ

0

1

q0/0

q0

q1

q1/1

q2

q0

q2/2...