Clase 13 - MEF-V1

Vista previa del material en texto

ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Una Máquina Secuencial o Máquina de Estados Finitos (MEF) es un caso
particular de una MT. Este modelo tiene como objetivo obtener una secuencia
de salida de igual longitud y en correspondencia con una secuencia de entrada,
pero que no depende solo de esta entrada sino del estado en el que se encuentre
el modelo. Esta máquina se corresponde con la solución de diversos problemas
algorítmicos relacionados en general con los sistemas de control.
Para su mejor comprensión lo representaremos con el siguiente esquema:
Cabezal de 
Lectura
e1 e2
••• ••• en-1 en
Cinta Finita de Entrada
s1 s2
••• ••• sn-1 sn
Cinta Finita de Salida
Control
0 1
2
X
3
.
. .Es
ta
d
o
s
Cabezal de 
Escritura
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Al comienzo se escribe en la cinta de entrada la palabra que se desea procesar (ei ), la
misma termina con un símbolo de fin de cadena que por simplicidad no consideraremos
en forma explícita y un cabezal de lectura que se encuentra sobre la posición del primer
símbolo de dicha palabra.
En general este modelo puede estar en cualquiera de sus estados cuando comienza a
funcionar y realiza las siguientes acciones:
1) LEE un símbolo de la cinta de entrada y mueve el cabezal de lectura a la derecha.
2) De acuerdo al ESTADO ACTUAL y al símbolo leído, transiciona a un NUEVO
ESTADO (que puede ser el mismo).
3) ESCRIBE un símbolo en la cinta de salida (si ) y mueve el cabezal de escritura a la
derecha. Para seleccionar el símbolo que escribe, existen dos criterios que derivan en
dos modelos para una MEF, que son totalmente equivalentes:
• MEALY: Elige el símbolo según el estado actual y el símbolo leído.
• MOORE: Elige el símbolo de acuerdo al estado nuevo al que transiciona.
4) Repite 1), 2) y 3) hasta que lee totalmente la palabra y se detiene.
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Definición formal de una Máquina Secuencial:
MEF =  Q , ΣE , ΣS , f , g 
Q : Conjunto finito y no vacío de estados.
ΣE : Alfabeto de símbolos de entrada.
ΣS : Alfabeto de símbolos de salida.
f : Función de control o transición, con f : Q x ΣE  Q
g : Función de salida, para MEALY g : Q x ΣE  ΣS
para MOORE g : Q  ΣS
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Representación formal de las funciones de transición y de salida:
Grafo de Transición y Salida Moore
q’/sq/..
e 
Grafo de Transición y Salida Mealy
q’q
e / s 
Matriz f /g Mealy
Q
ΣE
e1 …. em
q1 qi / sp …. qj / sr
…. …. ….
qn qh / sv …. qk / sw
Matriz f /g Moore
Q / ΣS
ΣE
e1 …. em
q1 / sp qi …. qj
…. …. ….
qn / sr qh …. qk
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Desde un punto de vista funcional podemos diferenciar los dos modelos como
sigue:
• En el modelo de Mealy la salida se realiza instantáneamente, es decir bien
que se lee un símbolo de la cinta de entrada y según el estado actual, se
escribe un símbolo en la cinta de salida. Por eso, en su implementación,
primero se debe obtener la salida y luego el estado nuevo.
• En el modelo de Moore la salida sufre un retardo, ya que se debe realizar
primero la transición a otro estado, según el símbolo leído y el estado
actual, para recién escribir un símbolo en la cinta de salida, que depende
solo del estado al que se ha transicionado. Por este motivo, en su
implementación, primero se debe obtener el estado nuevo y luego la salida.
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MEF1=  Q , ΣE , ΣS , f , g 
Q = { q0 , q1 , q2 } 
 E = { 0, 1 } 
S = { p, i, n }
Esta MEF termina escribiendo “n”, “p” o “i”, si la secuencia 
de entrada tiene solo “0”, una cantidad par de “1” o una 
cantidad impar de “1” respectivamente.
Grafo
0 1
q0 q0 / n q1 / i
q1 q1 / i q2 / p
q2 q2 / p q1 / i
Matriz
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MEF2 =  Q , ΣE , ΣS , f , g 
Q = { q0 , q1 , q2 } 
 E = { 0, 1 } 
S = { 0, 1 }
Esta MEF obtiene como respuesta el Complemento A2 del 
número binario natural que se coloca como entrada. 
Cabe aclarar que el número se introduce invertido.
Grafo
0 1
q0 / 0 q0 q1
q1 / 1 q1 q2
q2 / 0 q1 q2
Matriz
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MEF3 =  Q , ΣE , ΣS , f , g 
Q = { q0 , q1 } 
 E = { a, b } 
S = { R, A }
Esta MEF tipo Moore funciona como aceptor del lenguaje regular: 
(b*.a)*.b.b*. Cuando se termina de leer la secuencia de entrada, se
acepta si la última salida fue “A” y se rechaza si fue “R”.
Grafo
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
a b
q0 / R q0 q1
q1 / A q0 q1
Matriz
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
La descripción instantánea de una MEF requiere las siguientes
especificaciones:
✓ Estado actual de la MEF.
✓ Secuencia que falta leer de la cinta de entrada.
✓ Secuencia que se va escribiendo en la cinta de salida.
Esta terna constituye la CONFIGURACIÓN de la MEF y vamos a
representarla con la secuencia de símbolos que se van escribiendo en la cinta
de salida, seguida del estado actual y de la secuencia de símbolos que faltan
leer en la cinta de entrada: s1...si-1qkei...en
Una sucesión de configuraciones consecutivas se llama SECUENCIA DE
CONFIGURACIÓN de la MEF.
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Consideremos el ejemplo de la MEF1 y las secuencias:
w1 = 10101 , w2 = 00 , w3 = 011 , w4 = 10
Las secuencias de configuración correspondientes serían:
1) q010101 ├─ iq10101 ├─ iiq1101 ├─ iipq201
├─ iippq21 ├─ iippiq1 i/cantidad impar de “1” 
2) q000 ├─ nq00 ├─ nnq0 n/secuencia solo de “0”
3) q0011├─ nq011 ├─ niq11 ├─ nipq2 p/cantidad par de “1”
4) q010 ├─ iq10├─ iiq1 i/cantidad impar de “1”
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Consideremos el ejemplo de la MEF2 y los números binarios
10100, 00, 011 y 10; entonces las secuencias de entrada serían:
w1 = 00101 , w2 = 00 , w3 = 110 , w4 = 01
Las secuencias de configuración correspondientes serían:
1) q000101 ├─ 0q00101 ├─ 00q0101 ├─ 001q101
├─ 0011q11 ├─ 00110q2 CA2 = 01100 
2) q000 ├─ 0q00 ├─ 00q0 CA2 = 00
3) q0110├─ 1q110 ├─ 10q20 ├─ 101q1 CA2 = 101
4) q001 ├─ 0q01├─ 01q1 CA2 = 10
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Consideremos el ejemplo de la MEF3 y las palabras: 
w1 = aabbb , w2 = bb , w3 = aaa , w4 = baa
Las secuencias de configuración correspondientes serían:
1) q0aabab ├─ Rq0abab ├─ RRq0bab ├─ RRAq1ab
├─ RRARq1b ├─ RRARAq1 A/acepta
2) q0bb ├─ Aq1b ├─ AAq1 A/acepta
3) q0aaa ├─ Rq0aa ├─ RRq0a ├─ RRq0 R/rechaza
4) q0baa ├─ Aq1aa ├─ ARq0a ├─ ARRq0 R/rechaza
MÁQUINA DE ESTADOS FINITOS (MEF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Obtención de una MEF tipo Mealy a partir de una Moore:
Partimos de una MEF tipo Moore:
MO =  Q , ΣE , ΣS , f , g 
y construimos una MEF tipo Mealy:
ME = Q , ΣE , ΣS , f , g’ 
donde, por cada transición y salida en la 
que se cumpla:
f(q,e) = p , g(p) = s 
con q,pQ , eΣE , sΣS
se define g’(q,e) = s
Tomemos como ejemplo la MEF4 Moore:
Entonces la MEF Mealy equivalente es:
0 1 2
q0 / a q0 q1 q2
q1 / b q2 q0 q0
q2 / c q2 q1 q2
0 1 2
q0 q0 / a q1 / b q2 / c
q1 q2 / c q0 / a q0 / a
q2 q2 / c q1 / b q2 / c
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Obtención de una MEF tipo Moore a partir de una Mealy:
Partimos de una MEF tipo Mealy:
ME =  Q , ΣE , ΣS , f , g 
y construimos una MEF tipo Moore:
MO =  Q’ , ΣE , ΣS , f’ , g’ 
donde, por cada transición y salida en la 
que se cumpla:
f(q,e) = p , g(q,e) = s 
con q,pQ , eΣE , sΣS
se crea un estado ps Q’ con g’(ps) = s
y f’(px, e)= ps p/cada estado px, x ΣS
Si a un determinado estado qQ no 
llegan transiciones se crea el estado: q
Tomemos como ejemplo la MEF5 Mealy:
Entonces la MEF Moore equivalente es:
a b
q0
1 / 1 q0
1 q2
1
q1
 /  q2
0 q0
1
q2
0 / 0 q2
1 q2
0
q2
1 / 1 q2
1 q2
0
a b
q0 q0 / 1 q2 / 1
q1 q2 / 0 q0 / 1
q2 q2 / 1 q2 / 0
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Ejemplos de MEF con casos de la vida real:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos.