MQUINAS DE ESTADO FINITAS
Pablo San Segundo (C-206)
[email protected] Sistemas secuenciales
Secuencial = combinacional + memorias
(biestables)y k f ( x1k , x2k ,..., xnk , m1k , m2k ,...mmk )
Tipos
Sncrono: cambio de estado en cada ciclo de reloj.
Asncrono: cambio de estado nada mas detectarse
variaciones en las entradas o en las memorias internas.
Modelo formal: Mquina de estados
Mealy: las salidas
depende de las entradas y del valor de
m k k f ( x1k , x2k ,..., xnk , m1k , m2k ,...mmk )
las memorias
y k f ( x1k , x2k ,..., xnk , m1k , m2k ,...mmk )
m k k f ( x1k , x2k ,..., xnk , m1k , m2k ,...mmk )
k
Moore: las salidas slo
valor de las memorias
y k fdepende
(m1k , m2k ,...mdel
m)
Mquina de Mealy
Mquina de MEALY: Una mquina secuencial de tipo
MEALY es una 5-tupla M=(Q,I,O,,) donde:
Q es un conjunto finito de estados
I es un conjunto finito de entradas (smbolos de )
O es un conjunto finito de salidas (smbolos de )
: QxI Q es la funcin de transicin de estado
: QxI O es la funcin de salida
Q(T T ) ( IT , QT )
OT ( IT , QT )
O
COMBINACIONAL
Mquina de Moore
Mquina de MOORE: Una mquina secuencial de tipo
MOORE es una 5-tupla M=(Q,I,O,,) donde:
Q es un conjunto finito de estados
I es un conjunto finito de entradas (smbolos de )
O es un conjunto finito de salidas (smbolos de )
: QxI Q es la funcin de transicin de estado
Q O es la funcin de salida
I
COMBINACIONAL
Objetivos
Nociones de Mquinas de Moore y Mealy
Modelado
Diagramas de estado
Tablas de transicin
Simplificacin
Conversiones entre mquinas
Estados equivalentes
Aplicacin sobre el diagrama de estados
Aplicacin sobre las tablas de transicin
Diseo de sistemas secuenciales sncronos
Eleccin de estados (preferentemente con semntica de salida)
Simplificacin
Ecuaciones de transicin de estados
Activacin
Retencin
Casos prcticos
Ejemplo: Sumador binario bit a bit (1/4)
Entradas
Dos entradas binarias x1 y x2
Una salida binaria y
0 1 1 1 1
Estados- Maquina MEALY
q0 estado de no acarreo
q1 estado de acarreo 0
1 1 0 0
1 1 0 1 1
x2
Funcin de transicin de estado
Q = {q0,q1} donde
x1
(q0,11) = q1
(q1,00) = q0
(q0,00/01/10) = q0
(q1,10/01/11) = q1
Funcin de salida
(q0,00/11) = 0
(q1,00/11) = 1
(q0,01/10) = 1
(q1,01/10) = 0
IO
EJERCIC
ra y
a
p
d
a
d
r
e
v
Tablas de
Ejemplo: Sumador binario de 1 bit (2/4)
m={q0,q1}
N
CUESTI
cin
Interpreta
?
semntica
x1
x2
mt
mt+t
mt t x1 x2 x1mt x2 mt
y x1 x2 mt x1 x2 mt x1 x2 mt x1 x2 mt
Ejemplo: Sumador binario bit a bit (3/4)
0 1 1 1 1
x1
+
0 1 1 0 0
1 1 0 1 1
x2
Evento de ACTIVACIN
del estado q1
00/0
01,10/1
q0
11/1
11/0
00/1
q1
01,10/0
Diagrama de transicin de estados
Eventos de RETENCIN
del estado q0
ina
CUESTIN
s una mqu
e
e
u
q
e
tr
s
e
Demu
de Mealy
Ejemplo: Sumador binario bit a bit
Diseo-Mquina MOORE
estado
estado
estado
estado
de
de
de
de
0 1 1 0
no acarreo con salida y=0
no acarreo con salida y=1
acarreo con salida y=0
acarreo con salida y=1
1 1 0 1 1
x2
Funcin de transicin de estados
q00
q01
q10
q11
x1
Q = {q00,q01,q10,q11} donde
0 1 1 1 1
(4/4)
(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
Funcin de salida
(q00/q10) = 0
(q01/q11) = 1
n
versi
n
N
o
c
I
T
le
re
CUES otra posib aly a Moo
e
de Me
Indiqu
Representacin-Diagrama de estados (1/2)
Diagrama de estados
Grafo cuyos nodos representan estados y los arcos
cambios (transiciones) entre estados fruto de eventos
MEALY
CUESTIN I
MEALY o MOORE?
01,10/1
00/0
11/1
11/0
q0
00/1
q1
01,10/0
CUESTIN II
Secuencial o combinacional?
01,10
q01 /1
q10 /0
00
10,01
11
SUMADOR
EN SERIE DE
1 BIT
11
0 1 ,1 0
MOORE
q00 /0
0 1 ,1 0
00
q11/1
11
Representacin-Tabla de transicin
Tabla de transicin de estados
0 1 1 1 1
(2/2)
x1
y
Representacin tabular de las funciones de transicin de
+
estado y salida
SUMADOR EN SERIE DE 1 BIT
0 1 1 0 0
Modelo MEALY
1 1 0 1 1
x2
Modelo MOORE
q T |x00
1 x01
2
11 10 00 01 11 10 O q T |x1x 2
q0
q1
q10
q11
q0,0
q0,1
q01
q01
q0,1
q1,0
q10
q10
q1,0 q0,1
q1,1 q1,0
q11
qT T q10
q11 q10
q00 q00 q01 q10 q01 0
q01 q00 q01 q10 q01 1
0
1
qT T
CUESTIN
Razone si pueden existir problemas de
implementacin de la
mquina para este caso
La salida se computa a partir del
estado actual (Qt) y las entradas
Simplificacin- estados equivalentes (1/3)
ESTADOS EQUIVALENTES (intuicin)
Dos estados son equivalentes cuando para una
misma secuencia de entradas la mquina evoluciona
de la misma manera: pasa por los mismos estados y
presenta la misma salida en todo momento
Simplificacin-ejemplo
(2/3)
Reconocedor de cadenas 101
10101 una sola secuencia
Rec.(101)
...111011011
I: x={0,1}
O: y={0,1}
0/0
NADA
Cadena {101}
NO encontrada
Cadena {101}
encontrada
...001001000
1/0
1/0
II
IN
T
S
l?
E
CU
c i ona
a
n
i
b
Com
1/0
0/0
10
1/1
101
0/0
0/0
Estados:
NADA
1
10
101
ningn smbolo reconocido
subcadena 1 reconocida
subcadena 10 reconocida
cadena 101 reconocida
I
CUESTIN
oore?
Mealy o M
Simplificacin-ejemplo
(3/3)
Identificacin de estados equivalentes
ICIO
EJERC
0/0
e t ra n
Tabla d
1/0
1/0
NADA
1/0
0/0
10
1/1
101
Q\X
0/0
1/1
0/0
Control secuencial
con mquinas
sncronas
Conversin a Mquina de Moore
Q\X
x=0
x=1 y
Qn
Qn
Q1
Q1
Q10
Q1
Q10
Qn
Q101 0
Q101
Qn
Q1
NADA/0
sicin
x=0
x=1
Qn
Qn/0
Q1/0
Q1
Q10/0 Q1/0
Q10
Qn/0
Q101/1
Q101
Qn/0
Q1/0
1
1
1/0
1
0
10/0
0
0
No hay estados equivalentes
101/1
Ejercicio: Control de un carrito
LEY DE CONTROL
Un ciclo completo de
ida y vuelta tras cada
pulsacin de PON
Izqda
A
PON
Entradas
Dcha
(1/7)
Salidas
PON
Izq
Dcha
Tanteo con mquina de Moore: Un estado por
cada combinacin de salidas posibles con
sentido:
Reposo (R)
Derecha (D)
Izquierda (I)
Ecuaciones de transicin
E={Pon, A, B}
Q={R, D, I}
O= {Do, Io}
Pon
Qt\
00
0
00
1
01
0
01
1
10
0
10
1
11
0
11
1
0,0
1,0
x
01
1
11
0
x
11
1
0,1
O
0,0
1,0
x
11
1
0,1
O
00
0
00
1
01
0
I
Qt\
10
0
10
1
Ecuaciones de
retencin de estado
RR, DD, II
I
Qt\
Ecuaciones de
activacin de estado
DI, RD, IR
(2/7)
00
0
00
1
R
01
0
x
01
1
10
0
10
1
R
11
0
0,0
1,0
0,1
Ecuaciones de activacin
Qt\
00
0
00
1
01
0
R
I
10
0
10
1
01
1
(3/7)
x
R
11
0
11
1
0,0
1,0
0,1
Dt 1 Rt Pon A
Activacin del estado Derecha
I t 1 Dt (BA B )
Activacin del estado Izquierda
Activacin del estado ReposoRt 1 I t A
PON A
Reposo
Dcha
Izqda
Ecuaciones de retencin
Qt
(4/7)
00
0
00
1
01
0
01
1
10
0
10
1
11
0
11
1
0,0
1,0
0,1
Retencin del estado de reposo
Usando solo entradas y reposo(t)-el formalismo
Rt 1 Rt (( Pon A B) (Pon A B ) ( Pon
A B ) ...)
Usando entradas, reposo(t) y derecha(t+1),
programacin PLCs
Rt 1 Rt Dt 1
Retencin de D, I?
Ecuaciones de transicin finales
Qt
(5/7)
00
0
00
1
01
0
01
1
10
0
10
1
11
0
11
1
0,0
1,0
0,1
Activacin
Retencin
Dt 1 Rt A Pon Dt It 1
Trans. Derecha
I t 1 Dt B I t Rt 1
Trans. Izquierda
Trans. ReposoRt 1 I t A Rt Dt 1
Modificacin de especificaciones
(6/7)
Sucesivas pulsaciones de Pon alternan la
direccin del movimiento del carrito (si no
est en los extremos)
Qt
Activacin
00
0
00
1
01
0
R
I
Retencin
10
0
10
1
D
Qt
01
1
x
11
0
11
1
0,0
1,0
0,1
00
0
00
1
01
0
01
1
10
0
10
1
11
0
11
1
0,0
1,0
0,1
Nuevas ecuaciones de transicin
Qt
(7/7)
00
0
00
1
01
0
01
1
10
0
10
1
11
0
11
1
0,0
1,0
0,1
Activacin
Retencin
Trans. DerechaDt 1 Pon B ( Rt I t ) Dt I t 1
I t 1 Dt ( B Pon) I t ( Rt 1 Dt 1 )
Trans. Izquierda
Trans. ReposoRt 1 I t A Rt Dt 1
Ejercicio: Control de trfico en un sentido-A
e2
e1
q1
q2
q3
q4
q5
q6
q7
Disee una mquina de estados que permita detectar vehculos
que circulan en direccin contraria por una autova. Dicho sistema
tendr dos entradas e1 y e2 que sern las seales de dos clulas
fotoelctricas situadas a una distancia menor que 1) la longitud del
vehculo y 2) la separacin entre vehculos
Solucin
(e1,e2)
salida
Qt\
00
01
10
11
C1: no vehculo
NO
NO
SI
SC
C2: correcto
SC
NO
SC
SC
SC
C3: incorrecto
SI
NO
SI
SI
SI
NOt 1 ( SCt SI t ) E1 E 2 NOt (SI t 1 SC
t 1 )
SCt 1 NOt E1 SCt NOt 1
SI t 1 NOt E 2 SI t NOt 1
01,11,10
C3/0
00,11
00
01
C1/1
01,11,10
10
00
C2/1
EJERCICIO
Ecuaciones de salida
Ejercicio: Control de trfico en un sentido-B
e2
e1
q1
q2
q3
q4
q5
q6
q7
Disee una mquina de estados que permita detectar vehculos
que circulan en direccin contraria por una autova. Dicho sistema
tendr dos entradas e1 y e2 que sern las seales de dos clulas
fotoelctricas situadas a una distancia mayor que la longitud del
vehculo y menor que la separacin entre vehculos
Tabla de transicin (I)
(e1,e2)
Qt\
00
01
10
11
no vehculo
NO
NO
SI
SC
correcto
SC
VE
C
SC
SC
SI
VEI
SI
SI
VEI
VEI
SI
VE
C
VE
C
SC
incorrecto
vehculo entre sensores no ok
vehculo entre sensores ok
CUESTIN I
Es correcta la tabla?
CUESTIN II
Indique si existe un problema con el diseo
Tabla de transicin (II)
00
01
10
11
no vehculo
Qt\
(e1,e2)
correcto-10
NO
NO
SI-01
SC10
SC-10
SC00
SC10
SC-00
SC00
SC01
SC-01
NO
SC01
correcto-00
correcto-01
SI-01
CUESTI
NI
SI-00
Complete
la tabla
SI-10
0
0
CUESTIN II
n estado?
lg
a
r
a
c
fi
li
p
im
Se puede s
0
EJERCICIO
Ecuaciones de activacin y retencin para la mquina simplificada
Ejercicio: Control de un cilindro (1/3)
Realizar un automatismo para el control de un cilindro de doble
efecto con una electrovlvula 5/2 biestable. Se dispone de un
interruptor de inicio (I) y otro de parada (P), junto con dos
sensores de posicin S1 y S2, que detectan la compresin y
expansin del cilindro respectivamente.
Al activar I se realizarn ciclos completos de expansin/compresin
del cilindro hasta activar P, momento en que el cilindro volver al
reposo.
En reposo siempre estar comprimido el cilindro. La parada siempre
ser preferente.
Diseo de mquina de estado (2/3)
Qt
Entradas: {I, P, S1, S2}
Salidas: {A1 y A2} R
E
Estados
000
0
000
1
A1
A
2
C
{ Reposo (R), Expandiendo
(E), Comprimiendo (C)
}
conf. inicial del reposo
EJERCICIO I
Ecuaciones de salidas
I . Rt 1 Ct P S1 Rt Et 1
II . Et 1 Rt I S1 S2 P Ct S1 P Et Ct 1
III . Ct 1 Et S 2 Ct Et 1
Indica parada
preferente
EJERCICIO
II
Ecuacione
s en lengu
aje
de
contactos
(KOP)
Lenguaje KOP (3/3)
Rt 1 Ct P S1 Rt Et 1
Et 1 Rt I S1 S2 P Ct S1 P Et Ct 1
Ct 1 Et S 2 Ct Et 1
Ec. activacin
Ec. retencin
Tabla de transicin (II)-Solucin
00
01
10
11
no vehculo
Qt\
(e1,e2)
correcto-10
NO
NO
SI-01
SC10
SC-10
SC00
SC10
SC-00
SC00
SC01
SC-01
NO
SC01
SI-01
01
x
x10
SI-10
correcto-00
correcto-01
incorrecto-01
incorrecto-00
incorrecto-10
Qt\ SI-01
(e1,eSI-00
2)
NO SI-10
SI-00
00
SI-00
NONO
x
SI01/00
x 11 0 O
x
0
SI-10
SC- x x 0 1
10/00
SC10/00
SC10/00
SC-01
SC10/00
SC-01
NO
SC-01
Entorno S5-Bloque OB1
Entorno S5-Simulador
Simplificacin (1/3)
Estados equivalentes: Dado un autmata de estados
finitos A=(Q,I,O,,), dos estados qi, qj Q se dicen
equivalentes (qi,e) = (qj,e) e I y (qi) =(qj).
(MEALY (qi,e) = (qj,e) e I)
ESTADOS EQUIVALENTES (informal)
Dos estados son equivalentes cuando para una misma
secuencia de entradas la mquina evoluciona de la misma
manera: pasa por los mismos estados y presenta la misma
salida en todo momento
REDUCCIN DE AUTMATAS
Autmatas incompletamente especificados
Ejemplo: Detector de coches en sentido contrario
Especificar un sistema que permita detectar vehculos
que circulan en direccin contraria por una autova.
Dicho sistema tendr dos entradas e1 y e2 que sern las
seales de dos clulas fotoelctricas situadas a una
distancia menor que la longitud del vehculo y la
e2
separacin entre vehculos.
e1
q1
q2
q3
q4
q5
q6
q7
MEALY o MOORE?
REDUCCIN DE AUTMATAS
Estados compatibles: Dado un autmata de
estados finitos A=(Q,I,O,,) incompletamente
especificado, se dice que dos estados
qi, qj Q son compatibles qi ~ qj
Transitiva?
(1) (qi,e) = (qj,e) e I en el dominio
de especificacin
(2) (qi) = (qj) en el dominio de
especificacin
q1
q2
q3
q4
q5
q6
q7
00
q1
X
X
q1
X
X
q1
01
q5
X
q4
q4
q5
X
X
11
X
q3
q3
X
q6
q6
X
10
q2
q2
X
X
X
q7
q7
S
1
1
1
1
0
0
0
Condiciones de
retencin del estado?
Simplificacin de mquinas
Autmatas completamente especificados
Una vez construido un modelo:
Es posible reducir el nmero de estados?
coste de implementacin/ejecucin
manejabilidad del modelo
RELACION DE EQUIVALENCIA
Estados equivalentes: Dado un autmata de estados
finitos A=(Q,I,O,,), dos estados qi, qj Q se dicen
equivalentes (qi,e) = (qj,e) e I y (qi) =(qj).
(MEALY (qi,e) = (qj,e) e I)
Dos estados equivalentes son INDISTINGUIBLES
El comportamiento del autmata a partir de
cualquiera de los dos estados es el mismo.
REDUCCIN DE AUTMATAS
q1 -> C1 (sistema en reposo)
q2, q3, q4 -> C2 (coche en sentido permitido)
q5, q6, q7 -> C3 (coche en sentido contrario)
00
C1 C1
C2 C1
C3 C1
01,11,10
C3/0
01
C3
C2
C3
11
X
C2
C3
00,11
00
01
C1/1
10
C2
C2
C3
S
1
1
0
01,11,10
10
00
Mealy/Moore?
C2/1
SINCRONISMO vs ASINCRONISMO
01,11,10
C3/0
00,11
00
01
C1/1
01,11,10
10
00
C2/1
Tipo de Entradas?
Tipo de Salidas?
CDIGO NO ESTRUCTURADO
Difcil puesta a punto y mantenimiento
void main (void) {
//...
C1:
Genera (NO_ALARMA) ;
Entrada = Leer_Entrada () ;
if (Entrada == I01) goto C3 ;
if (Entrada == I10) goto C2 ;
goto C1 ;
C2:
Genera (NO_ALARMA) ;
Entrada = Leer_Entrada () ;
if (Entrada == I00) goto C1 ;
goto C2 ;
C3:
Genera (ALARMA) ;
Entrada = Leer_Entrada () ;
if (Entrada == I00) goto C1 ;
goto C3 ;
//...
return ;
}
SINCRONISMO vs ASINCRONISMO
0/0
void main (void)
{
while (1)
{
[Espera_Sincronismo ();]
Entrada Sncrona
Entrada = Leer_Bit ();
switch (Estado)
{
case NADA : if (Entrada==0) {Salida=0; Estado=NADA;}
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;}
break ;
case E10 : if (Entrada==0) {Salida=0; Estado=NADA;}
else if (Entrada==1) {Salida=1; Estado=E101;}
break ;
case E101 : if (Entrada==0) {Salida=0; Estado=NADA;}
else if (Entrada==1) {Salida=0; Estado=E1;}
break ;
}
Genera (Salida) ;
}
return ;
}
NADA
1/0
1/0
0/0
0/0
1/1
Retencin
del estado
Salidas
Sncronas
10
SINCRONISMO vs ASINCRONISMO
Reconocedor de cadenas con entrada de validacin
0
NADA/0
1
1
1/0
1
0
10/0
0
0
Salida
0
1
101/1
void main (void)
{
while (1)
{
Espera_Sincronismo () ;
Entrada = Leer_Bit () ;
switch (Estado)
{
case NADA : ...
...
}
Genera (Salida) ;
}
return ;
}
Introduccin
lgebra booleana
Representacin
Tablas de verdad
Puertas lgicas
Axiomas
Simplificacin
Ejemplos
Mquinas de estados
Mealy
Moore
Representacin
Tablas de transicin
Diagramas de estados
Simplificacin (Reduccin)
Sincronismo
Ejemplos
REPASO: S.E.D.
SISTEMAS DE EVENTOS DISCRETOS
ESTADO
CONTINUO
DISCRETO
Sistemas
Continuos
oAnalgicos
Sistemasde
EventosDiscretos
Asncronos
DISCRETO
TIEMPO
CONTINUO
Sistemasde
TiempoDiscreto
oMuestreados
Sistemasde
EventosDiscretos
Sncronos
