máquinas de estadosmáquinas de estados · pdf filemáquinas de estados...

Máquinas de estados finitas 1

MÁQUINAS DE ESTADOSMÁQUINAS DE ESTADOS FINITASFINITAS


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


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


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


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


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


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


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


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


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.


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


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


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


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


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


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


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


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)


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?


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 ;

}


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


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 ;

}


FINFIN

máquinas de estadosmáquinas de estados · pdf filemáquinas de estados...

Documents