Máquinas de estados finitas 1
MÁQUINAS DE ESTADOSMÁQUINAS DE ESTADOS FINITASFINITAS
Máquinas de estados finitas 2
INTRODUCCIÓNEvento discreto: ocurrencia de una característica en la evolución de una señal (flanco de subida, paso por un cierto nivel, pulso, llegada de un dato )dato, …).
CONTINUO DISCRETO
ESTADO
Eventos discretos
SistemasContinuos
o Analógicos
Sistemas deEventos Discretos
AsíncronosNTI
NU
O
g
TIE
MPO
Sistemas de Sistemas deC
ON
ETO
Tiempo Discretoo Muestreados
Eventos DiscretosSíncronos
DIS
CR
E
Máquinas de estados finitas 3
INTRODUCCIÓNSistemas de eventos discretos: sistemas dinámicos que cambian de estado ante la ocurrencia de eventos discretos. Generalmente el estado sólo puede adquirir un conjunto discreto de valores y puede sersólo puede adquirir un conjunto discreto de valores y puede ser representado de forma simbólica en vez de numérica.
Ejemplo: encendidaEjemplo:accionamiento
interruptoraccionamiento interruptor
• Tiempo contínuo (sistemas asíncronos)
apagada
El estado del sistema puede cambiar en cualquier instante ante la llegada de un evento. Ej.: accionamiento del interruptor.
• Tiempo discreto (sistemas síncronos)• Tiempo discreto (sistemas síncronos)
El estado del sistema sólo cambia cada T sg en función del estado y entradas presentes en esos instantes de tiempo. Evento: señal de reloj. p p jEj.: intermitente.
O bien con un evento de sincronización -> validación
Máquinas de estados finitas 4
CONCEPTO DE AUTÓMATA. MODELOSModelo de MEALY
Má i d MEALY U á i i l d tiMáquina de MEALY: Una máquina secuencial de tipo MEALY es una 5-tupla M=(Q,I,O,δ,β) donde:
Q Ø es un conjunto finito de estadosQ ≠ Ø es un conjunto finito de estadosI ≠ Ø es un conjunto finito de entradas (símbolos de …)O ≠ Ø es un conjunto finito de salidas (símbolos de …)δ: QxI → Q es la función de transición de estadoδ: QxI → Q es la función de transición de estadoβ: QxI → O es la función de salida
I Oβ
Qβ
δ COMBINACIONAL
Máquinas de estados finitas 5
CONCEPTO DE AUTÓMATA. MODELOSModelo MOORE
Máquina de MOORE: Una máquina secuencial de tipo MOORE es una 5-tupla M=(Q,I,O,δ,λ) donde:
Q ≠ Ø es un conjunto finito de estadosI ≠ Ø es un conjunto finito de entradas (símbolos de …)O ≠ Ø es un conjunto finito de salidas (símbolos de …)
Q I Q l f ió d t i ió d t dδ: QxI → Q es la función de transición de estadoλ: Q → O es la función de salida
I OI Oλδ Q
COMBINACIONAL
Máquinas de estados finitas 6
CONCEPTO DE AUTÓMATA. MODELOSEjemplo: Sumador binario serie de 1 bit
• Dos entradas binarias x1 y x2y
• Una salida binaria y
Modelo MEALYx1
… 1 1 1 10
Modelo MEALY
• Q = {q0,q1} donde
0 t d d
…y
x
1 1 101+
q0 → estado de no acarreo
q1 → estado de acarreo
2x… 1 10 0 0
• Función de transición de estado:
δ(q0,11) = q1 δ(q0,00/01/10) = q0
δ(q1,00) = q0 δ(q1,10/01/11) = q1
• Función de salida:
β(q0,00/11) = 0 β(q0,01/10) = 1
β(q1,00/11) = 1 β(q1,01/10) = 0
Máquinas de estados finitas 7
CONCEPTO DE AUTÓMATA. MODELOSModelo MOORE
• Q = {q00,q01,q10,q11} donde … 1 1 1 10{q q q q }
q00 → estado de no acarreo con salida y=0
q01 → estado de no acarreo con salida y=1…
y
x1
1 1 10
1 1 1 10
1+q y
q10 → estado de acarreo con salida y=0
q11 → estado de acarreo con salida y=1
2x… 1 10 0 0
q11 → estado de acarreo con salida y 1
• Función de transición de estado:
δ(q00/q01 00) = q00 δ(q00/q01 11) = q10δ(q00/q01 ,00) = q00 δ(q00/q01 ,11) = q10
δ(q10/q11 ,00) = q01 δ(q10/q11 ,11) = q11
δ(q00/q01 01/10) = q01 δ(q10/q11 01/10) = q10δ(q00/q01 ,01/10) = q01 δ(q10/q11,01/10) = q10
• Función de salida:
( / ) ( / )λ(q00/q10) = 0 λ(q01/q11) = 1
Máquinas de estados finitas 8
REPRESENTACIÓN Y MODELADOTabla de transición
• Representación tabular de las funciones de transición de estado y p ysalida
SUMADOR EN SERIE DE 1 BIT
Modelo MEALY Modelo MOOREq q
00 01 11 10 00 01 11 10 Oq0 q0,0 q0,1 q1,0 q0,1 q00 q00 q01 q10 q01 0q1 q0,1 q1,0 q1,1 q1,0 q01 q00 q01 q10 q01 1
Tq Tq
q1 q0,1 q1,0 q1,1 q1,0 q01 q00 q01 q10 q01 1q10 q01 q10 q11 q10 0q11 q01 q10 q11 q10 1T Tq +Δ
T Tq +Δ
Diseño: La salida se computa a partirDiseño: La salida se computa a partir del estado actual y las entradas
Máquinas de estados finitas 9
REPRESENTACIÓN Y MODELADODiagrama de transición
• Grafo cuyos nodos representan estados y los arcos cambios de y p yestado.
M d l MEALY
00/0 11/1
Modelo MEALYq0 q1
11/0
00/101,10/001,10/1
00 11 10 01q00 /0 q /0
SUMADOR EN SERIE DE 1 BIT
Modelo MOORE
00 10,01
0 0 0 0
q00 /0 q10/0
00
01,10 11
00 11
01,1
0
00 1101,10 q11/1q
01 /1
Máquinas de estados finitas 10
REDUCCIÓN DE AUTOMATASAutómatas completamente especificados
• Una vez construido un modelo:
¿Es posible reducir el número de estados?
– ↓ coste de implementación/ejecuciónp j
– ↑ manejabilidad del modelo RELACION DE EQUIVALENCIA
Estados equivalentes: Dado un autómata de estados finitos A=(Q,I,O,δ,λ), dos estados qi, qj ∈ Q se dicen equivalentes ⇔ δ(qi,e) = δ(qj,e) ∀e ∈ I y λ(qi) =λ(qj). q (q , ) (qj, ) y (q ) (qj)(MEALY β(qi,e) = β(qj,e) ∀e ∈ I)
• Dos estados equivalentes son INDISTINGUIBLES
• El comportamiento del autómata a partir de cualquiera de los dos estados es el mismo.
Máquinas de estados finitas 11
REDUCCIÓN DE AUTÓMATASReconocedor de cadenas 101
x y
…10101 una sola secuencia
• I: x={0 1}
Rec.(101)x y
...111011011 ...001001000
0/0 1/0 1/0• I: x={0,1}
• O: y={0,1}NADA 1 10 101
1/0
1/0 0/0 1/1
0/00/0
Cadena no encontrada Cadena
encontrada
Estados: NADA nada reconocido
1 subcadena 1 reconocida
10 subcadena 10 reconocidaMealy/Moore?
101 cadena 101 reconocidaAnálisis
computacional
Máquinas de estados finitas 12
REDUCCIÓN DE AUTÓMATASIdentificación de estados equivalentes
0/0 1/0
NADA 1 10 101
0/0 1/0
1/0 0/0 1/1
1/0
0/0
0/0
1/1
x=0 x=1Qn Qn/0 Q1/0Q Q /0 Q /00/0 Q1 Q10/0 Q1/0Q10 Qn/0 Q101/1Q101 Qn/0 Q1/0Control secuencial
Conversión a Máquina de Moore0 1 1
101 n 1
x=0 x=1 y
Control secuencialMáquinas Síncronas
NADA/0 1/0 10/0 101/11 0 1
0
Qn Qn Q1 0Q1 Q10 Q1 0Q Q Q 0 0Q10 Qn Q101 0Q101 Qn Q1 1 No hay estados equivalentes
Máquinas de estados finitas 13
REDUCCIÓN DE AUTÓMATASAutómatas incompletamente especificados
• Ejemplo: Detector de coches en sentido contrarioj p
Especificar un sistema que permita detectar vehículos que circulan endirección contraria por una autovía. Dicho sistema tendrá dos entradas e1y e2 que serán las señales de dos células fotoeléctricas situadas a unay e2 que serán las señales de dos células fotoeléctricas situadas a unadistancia menor que la longitud del vehículo y la separación entrevehículos.
e1
e2
q1 q2 q3 q4
¿MEALY o MOORE?¿MEALY o MOORE?
q5 q6 q7
Máquinas de estados finitas 14
REDUCCIÓN DE AUTÓMATAS
Estados compatibles: Dado un autómata de estados finitos A=(Q,I,O,δ,λ) incompletamente
ifi d di d t d Transitiva?especificado, se dice que dos estados qi, qj ∈ Q son compatibles qi ~ qj ⇔
(1) δ(qi e) δ(qj e) ∀e I en el dominio
Transitiva?
(1) δ(qi,e) = δ(qj,e) ∀e ∈ I en el dominio de especificación
(2) λ(qi) λ(qj) en el dominio de(2) λ(qi) = λ(qj) en el dominio de especificación
Condiciones de retención del
estado?
00 01 11 10 Sq1 q1 q5 X q2 1q2 X X q3 q2 1q q qq3 X q4 q3 X 1q4 q1 q4 X X 1q5 X q5 q6 X 0q6 X X q6 q7 0q7 q1 X X q7 0
Máquinas de estados finitas 15
REDUCCIÓN DE AUTÓMATASAlgoritmo
GRAFO DE COMPATIBILIDAD
Algoritmo para reducción
1)Construir el grafo de C2C1q1
q2
compatibilidad binaria
2)Encontrar el mayor subgrafo completo S en el grafo (estados compatibles)
2C1
q7
compatibles)
3)Borrar S y volver al paso 2 hasta que todos los vértices estén agrupados
q6
q3
q5
q4C3Análisis de
complejidad
Máquinas de estados finitas 16
REDUCCIÓN DE AUTÓMATASReducción de estados
q1 -> C1 (sistema en reposo)
q2,q3,q4 -> C2 (coche en sentido permitido)
q5,q6,q7 -> C3 (coche en sentido contrario)
00 01 11 10 SC1 C1 C3 X C2 1C1 C1 C3 X C2 1C2 C1 C2 C2 C2 1C3 C1 C3 C3 C3 0
00,11 01,11,1001,11,10
C1/1C3/0 C2/110
01
00
00
Mealy/Moore?
01 00
Máquinas de estados finitas 17
IMPLEMENTACIÓN-ENTRADAS• Eventos -> espera a su llegada para que evolucione el sistema
Muestreo encendidoapagado
Interrupciónencendido
encendidoapagado
• Entradas de nivel
Lectura asíncrona
apagado
Lectura asíncrona
– Las entradas se leen conforme se vayan necesitando en el control (ciclo de tratamiento)
– Aleatoriedades / TransitoriosL t íLectura síncrona
– Se leen todas las entradas a la vez
M i I– Memoria Imagen
Máquinas de estados finitas 18
IMPLEMENTACIÓN-SALIDAS
• Impulsionaleser/set(oj) em/clear(oj)
p
Asociadas a cambios de estados / Modelo MEALY
• De nivel o mantenidas es/set(oj) en/clear(oj)
qi
De nivel o mantenidas
Asociadas a estados / Modelo MOOREer em
es/set(oj) en/clear(oj)
em
qi/oj
• Generaciónes en
En el instante en que se calculan (asíncrona)
Todas al final del tratamiento (síncrona)
Máquinas de estados finitas 19
IMPLEMENTACIÓNEjemplo: Detector sentido contrario void main (void) {
//...C1:
Genera (NO_ALARMA) ;Entrada = Leer_Entrada () ;if (Entrada == I01) goto C3 ;if (Entrada == I10) goto C2 ;ggoto C1 ;
C2:Genera (NO_ALARMA) ;Entrada = Leer Entrada () ;
00,11 01,11,10
1000
01,11,10
_if (Entrada == I00) goto C1 ;goto C2 ;
C3:Genera (ALARMA) ;
C1/1C3/0 C2/101 00
Entrada = Leer_Entrada () ;if (Entrada == I00) goto C1 ;goto C3 ;CÓDIGO NO ESTRUCTURADO
//...return ;
}
Difícil puesta a punto y mantenimiento
Tipo de Entradas? Tipo de Salidas?
Máquinas de estados finitas 20
IMPLEMENTACIÓNCiclo de tratamiento
Ej.: Detección void main (void) jsentido contrario
MOORE
{while (1){Entrada = Leer_Entrada () ;
Entradas nivel síncronas
S lid
_Estado = Sig_Estado ;switch (Estado){case C1 : Genera (NO_ALARMA) ;
Salidas asíncronas
_switch (Entrada) {case I01 : Sig_Estado = C3 ; break ;case I10 : Sig_Estado = C2 ; break ;default : ;}
break ;case C2 : Genera (NO_ALARMA) ;
if (Entrada == I00) Sig_Estado = C3 ;break ; ¿Salidas
case C3 : Genera (ALARMA) ;if (Entrada == I00) Sig_Estado = C1 ; break ;
}
¿Salidas síncronas?
}return ;
}
Máquinas de estados finitas 21
IMPLEMENTACIÓNEj: Reconocedor de cadenas
void main (void) 0/0 1/0
{while (1) {[Espera_Sincronismo ();]
d i ()
NADA 1 101/0 0/0
0/0Entrada Entrada = Leer_Bit ();switch (Estado){case NADA : if (Entrada==0) {Salida=0; Estado=NADA;}
l if ( d 1) {S lid 0 d 1 }
1/1Síncrona
else if (Entrada==1) {Salida=0; Estado=E1;}break ;
case E1 : if (Entrada==0) {Salida=0; Estado=E10;}else if (Entrada==1) {Salida=0; Estado=E1;}b k
Máquina de Mealy
break ; case E10 : if (Entrada==0) {Salida=0; Estado=NADA;}
else if (Entrada==1) {Salida=1; Estado=E101;}break ;
E101 if (E t d 0) {S lid 0 E t d NADA }
Retención
case E101 : if (Entrada==0) {Salida=0; Estado=NADA;}else if (Entrada==1) {Salida=0; Estado=E1;}break ;
}G (S lid )
Salidas SincronasGenera (Salida) ;
}return ;
}
Sincronas
Máquinas de estados finitas 22
IMPLEMENTACIÓNReconocedor de cadenas con entrada de validación
0 1 1
1 0 1
void main (void) {
while (1)
NADA/0 1/0 10/0 101/11 0 1
0
0 ( ){Espera_Sincronismo () ;Entrada = Leer_Bit () ;switch (Estado)
0
Salida
( ){case NADA : ......
}0
1
Genera (Salida) ;}return ;
}
Máquinas de estados finitas 23
FINFIN