1. No category

10. Máquinas de Estado Finito
Las máquinas de estado finito, llamadas también autómatas finitos son modelos matemáticos que constituyen una importante herramienta en el diseño de circuitos físicosecuenciales, en el estudio de los lenguajes formales y de compiladores e intérpretes de
varios lenguajes de programación.
Mientras que en un circuito combinacional la salida depende únicamente de la entrada
en ese instante, una máquina secuencial es un sistema que acepta unas entradas y genera
unas salidas en instantes de tiempo discretos. La salida en cada instante dependerá de la
condición interna (estado) de la máquina en ese instante y de la entrada actual al sistema.
Por otro lado, la entrada y el estado en cierto instante determinan el estado que la máquina
tendrá en el instante siguiente.
Todas las máquinas de estado finito tienen un conjunto de estados, un estado inicial, un
alfabeto fuente y una función de transición que a cada pareja de estado y dato de entrada le
asigna el estado siguiente. Los estados de la máquina le dan unas capacidades de memoria
limitadas. Algunas máquinas de estado finito producen un símbolo como dato de salida
para cada transición y pueden utilizarse para modelar gran variedad de máquinas, en las
que se incluyen las máquinas expendedoras, los semáforos, los sumadores binarios, y
los reconocedores de lenguaje. También estudiaremos máquinas de estado finito que no
generan datos de salida, pero tienen estados finales. Estas máquinas (autómatas) se utilizan
con gran frecuencia en el reconocimiento de lenguajes. Las cadenas que se reconocen son
aquellas que transforman el estado inicial en un estado final. Los conceptos de gramática y
máquina de estado finito pueden relacionarse entre sí. De hecho, los conjuntos que son
reconocidos por una máquina de estado finito son los conjuntos generados por cierto tipo
de gramática.
Capítulo 10. Máquinas de Estado Finito
28
10.1
Estados
Cada etapa que atraviesa un circuito secuencial se denomina estado. En cada estado, el
circuito almacena un recuerdo de su historia pasada, para saber qué hacer a continuación.
Un estado se distingue de otro por sus recuerdos almacenados. Parecerá que, a medida que
progresa el tiempo, es necesario añadir nuevos elementos a la memoria y, por consiguiente,
desarrollar una secuencia ilimitada de estados nuevos y diferentes. Sin embargo, parece
que ni toda la historia pasada es relevante, ni todos los estados por los que progresa el
sistema son diferentes entre sí y que el número total de estados es bastante limitado.
Ejemplo 10.1 — Máquina expendedora de dulces. Supongamos que una máquina
expendedora tiene dos tipos de productos A y B. El precio de cada producto es de 200
pesos. La máquina admite únicamente monedas de 100 y 200 pesos y devuelve el cambio
de necesario. Dispone de un botón rojo que expide el producto A y uno verde que hace
lo mismo con el producto B. Carlos quiso comprar el producto A y para ello introdujo
consecutivamente dos monedas de 100 pesos. Luego, apretó el botón rojo y obtuvo el
producto deseado. Representamos el proceso con la tabla 10.1, donde t0 es el instante
inicial cuando inserta su primera moneda y ti con i = 1, 2, 3 son los instantes posteriores.
�
t0
Estado Actual
Entrada
Salida
Próximo Estado
t1
t2
t3
s0
s1
s2
s0
$100 $100 Botón rojo
Nada Nada Producto A
s1
s2
s0
Cuadro 10.1: Proceso de la máquina expendedora de dulces
La máquina está en un estado de espera en el estado s0 : espera a que un cliente
comience a insertar monedas hasta un total de $200 pesos o más y oprima el botón para
obtener el producto deseado. Si en cualquier momento del proceso, el total de monedas
insertadas supera los $200 pesos, la máquina devuelve el cambio necesario antes de que el
cliente oprima el botón correspondiente.
Estando la dispensadora en el estado s0 , ocurre el instante t0 en el cual Carlos inserta
una moneda de $100 y no recibe nada. Ahora, la máquina pasa a un estado s1 el cual indica
que tiene almacenados 100 pesos y que está a la espera de otra moneda.
Luego ocurre el instante t1 : Carlos inserta otra moneda de $100 y otra vez, no recibe
nada. La máquina ha pasado al estado s2 que indica que tiene almacenados $200 pesos
pero todavía no sabe qué tipo de producto quiere Carlos.
Al oprimir el botón rojo en el instante t2 , la máquina expide el producto A y en el
siguiente instante se coloca de nuevo en el estado inicial s0 (ninguna moneda almacenada).
Las características de esta máquina son:
En un instante dado, la máquina sólo puede estar en un estado de un conjunto finito
de estados internos posibles.
La máquina sólo acepta un número finito de entradas (en el ejemplo, monedas de
100 y 200 pesos, botones rojo y verde).
Mediante cada combinación de entrada y estado interno, se produce una salida y un
estado siguiente. El conjunto de salidas, para nuestra máquina es nada, monedas de
100 y 200 pesos y productos A y B.
10.2 Máquinas de Estado Finito con Salida
29
Los procesos de la máquina son secuenciales y se producen en instantes distintos.
La máquina es determinista ya que la salida queda determinada por el estado y la
entrada.
�
10.2
Máquinas de Estado Finito con Salida
Definición 10.2.1 Una máquina de estado finito con salida, M = (S, I, O, f , g, s0 ), con-
siste en un conjunto finito de estados S, un alfabeto (conjunto finito no vacío) de entradas
I, un alfabeto de salidas O, un estado inicial s0 , una función de transición f : S × I −→ S
y una función de salida g : S × I −→ O.
Las máquinas de este tipo se llaman máquinas de Mealy porque fue G. H. Mealy, en
1955, el primero que las estudió. Hay otro tipo importante de máquina de estado finito con
salida, donde la salida está determinada sólo por el estado. Este tipo de máquina se llama
máquina de Moore en honor a E. F. Moore, quien la definió en 1956.
Una máquina M = (S, I, O, f , g, s0 ) puede describirse por una tabla de estados, que
indica los valores de las funciones f y g, o por un diagrama de estados, grafo dirigido
donde los vértices representan los estados de la máquina. El estado inicial se indica
mediante una flecha que no proviene de otro estado y existe una flecha, etiquetada por
“i,o”, del estado s al estado s� si f (s, i) = s� y g(s, i) = o, como se muestra en la figura 10.1.
Figura 10.1: Conexión entre dos estados
�
Ejemplo 10.2 La tabla 10.2 corresponde a la tabla de estados del ejemplo 10.1.
Estados
s0
s1
s2
Transición
Salida
$100
Entrada
$200 Rojo
Verde
$100
Entrada
$200 Rojo
s1
s2
s2
s2
s2
s2
s0
s1
s0
Nada
Nada
$100
Nada
$100
$200
s0
s1
s0
Verde
Nada Nada
Nada Nada
A
B
Cuadro 10.2: Tabla de estados de la máquina expendedora de dulces
El correspondiente diagrama de estados sería aquel mostrado en la figura 10.2.
�
�
Ejemplo 10.3 — Máquina generadora de retardo. Se quiere diseñar una máquina
de estado finito con una unidad de retardo que, dada una cadena de entrada x = x1 ...xk
devuelva 0x1 ...xk−1 .
La máquina inicia en un estado s0 . Este estado indica que la máquina está a la espera
de entradas. En este estado pueden llegar dos entradas: ‘0’ y ‘1’. Si llega un ‘1’, la máquina
30
Capítulo 10. Máquinas de Estado Finito
Figura 10.2: Diagrama de Estados de la máquina expendedora de dulces
pasará al estado s1 el cual indica que hay acumulado un ‘1’ al tiempo que arroja una
salida: ’0’. Si en cambio llegase un ‘0’, la máquina pasaría del estado s0 al estado s2 el cual
indica que hay acumulado un ’0’ al tiempo que arroja una salida: ‘0’. Hasta el momento la
máquina es la mostrada en la figura 10.3
Figura 10.3: Construcción del Generador de Retrardos
Ahora, estando en s1 , sin importar el valor de la entrada, la salida será el ‘1’ que estaba
acumulado en ese estado. De forma similar, estando en s2 , sin importar el valor de la
entrada, la salida será el ‘0’ que estaba acumulado en ese estado. Si la entrada es ‘1’ -desde
ambos estados-, esta deberá acumularse en el estado s1 y si la entrada es ‘0’ -desde ambos
estados-, deberá acumularse en el estado s2 .
El diagrama final del generador de retardo se presenta en la figura 10.4.
�
� Ejemplo 10.4 — Máquina generadora de dos unidades de retardo. Se quiere
diseñar una máquina de estado finito con dos unidades de retardo que, dada una cadena de
10.2 Máquinas de Estado Finito con Salida
31
Figura 10.4: Diagrama de Estados del Generador de Retrardos
entrada x = x1 ...xk devuelva 00x1 ...xk−2 .
Antes de comenzar. Recuerde que en la máquina de estados del ejemplo 10.3 se
acumulaba un solo dígito (‘0’ o ‘1’). Por esta razón, sólo se necesitaba un total de 3 estados:
2 estados de “tránsito” más un estado de inicio (al cual no se volvía, una vez comenzada la
secuencia). Pues, bueno, esta vez haremos algo similar. Como necesitamos acumular dos
dígitos (“00”, “01”, “10” o “11”) necesitamos un total de 5 estados: 4 estados de “tránsito”
más un estado inicial. El esqueleto del diagrama de estados se muestra en la figura 10.5.
Diseñemos la máquina de estados finitos a partir de una secuencia de entrenamiento
cualquiera como: “00001111011000010�� .
Figura 10.5: Esqueleto del Diagrama de Estados del Generador de dos unidades de Retrardos
Para ayudarnos un poco, en la tabla 10.3 se muestran los dígitos acumulados, los que
Capítulo 10. Máquinas de Estado Finito
32
vamos imprimiendo y los que van llegando.
Llegó
Acumulado
00
Impreso
Cuadro 10.3: Tabla de ayuda
Tenga en cuenta que antes de que comiencen a llegar dígitos a la máquina, esta ya tiene
dos ceros acumulados: “00”. Empecemos, pues, con la secuencia de entrenamiento:
El estado inicial de la máquina es s0 . Cuando llega el primer ‘0’, se imprime el primer
dígito acumulado que, en este caso, también es cero. Ahora, se tendrá acumulado de nuevo
un “00”. En la tabla 10.4 se muestra el estado actual del sistema.
Llegó
0
Acumulado
0✁ 00
Impreso
0
Cuadro 10.4: Tabla de ayuda
Cuando llega el siguiente ‘0’, se imprime el primer dígito acumulado (‘0’) y todavía se
tiene acumulado un “00”. Al sistema llegan otros dos ceros. Esto provoca que se impriman
dos nuevos ceros y que se acumulen dos ceros. En la tabla 10.5 se muestra el estado actual
del sistema.
Llegó
0000
Acumulado
✘✘
✘
000000
Impreso
0000
Cuadro 10.5: Tabla de ayuda
Ahora, cuando llega el primer ‘1’, se imprime el primer dígito acumulado (‘0’) y se
tendrá acumulado un “01”. Si llega otro ‘1’, se imprimirá el primer dígito acumulado (‘0’)
y quedará acumulado un “11”. En la tabla 10.6 se muestra el estado actual del sistema.
Llegó
000011
Acumulado
✘✘✘
00000011
✘
Impreso
000000
Cuadro 10.6: Tabla de ayuda
Se puede ver que cada estado indica los dígitos que hay acumulados. En la figura 10.6
se muestra el estado actual del diagrama de estados.
10.2 Máquinas de Estado Finito con Salida
33
Figura 10.6: Diagrama de Estados del generador de dos unidades de retardo
Al llegar un nuevo ‘1’, se imprimirá el primer dígito acumulado (‘1’) y quedará
acumulado nuevamente un “11”. Al sistema llegan otros dos unos. Esto provoca que se
impriman dos nuevos unos y que se acumulen dos unos. Al llegar un ‘0’, se imprimirá el
primer dígito acumulado (‘1’) y ahora quedará acumulado un “10”. En la tabla 10.7 se
muestra el estado actual del sistema y en la figura 10.7 se muestra el estado actual del
diagrama de estados.
Llegó
0000111110
Acumulado
✭
✭✭
✭✭✭
000000111110
✭
Impreso
0000001111
Cuadro 10.7: Tabla de ayuda
Figura 10.7: Diagrama de Estados del generador de dos unidades de retardo
Al llegar un ‘1’, se imprimirá el primer dígito acumulado (‘1’) y ahora quedará
acumulado un “01”.
Capítulo 10. Máquinas de Estado Finito
34
Se puede verificar que con el resto de la secuencia de entrenamiento se consigue el
diagrama de estados de la figura 10.8 y la tabla 10.8.
Llegó
00001111011000010
Acumulado
✭✭✭
00000011111011000010
✭✭✭✭
Impreso
000000111110110000
✭✭✭✭
Cuadro 10.8: Tabla de ayuda
Figura 10.8: Diagrama de Estados final del generador de dos unidades de retardo
El salto de s0 a s2 se consigue cuando al iniciar la secuencia se ingresa un ‘1’ en vez de
un ‘0’.
�
Ejercicio 10.1 — Generador de Retrasos Avanzado. Diseñe una máquina de estado
finito con tres unidades de retardo que, dada una cadena de entrada x = x1 ...xk devuelva
010x1 ...xk−3 .
�
10.3
Autómata finito
Un autómata finito (determinista) es un modelo matemático de una máquina que
permite saber si una cadena de símbolos pertenece o no a un lenguaje definido sobre cierto
alfabeto. Consiste en un conjunto finito de estados y un conjunto de transiciones entre
estos estados, que dependen de los símbolos de la cadena de entrada. El autómata acepta
una cadena de entrada si al terminar de leer todos los símbolos de esa cadena la máquina
está en alguno de los posibles estados finales; si el estado no es final, entonces la cadena
no pertenece al lenguaje que reconoce la máquina.
10.3 Autómata finito
35
Definición 10.3.1 Un autómata de estado finito M = (S, I, f , s0 , F) consiste en un
conjunto finito de estados S, un alfabeto de entradas I, un estado inicial s0 , una función
de transición f : S × I → S y un conjunto F de estados finales o de aceptación (F ⊆ S).
En el diagrama de transición de un autómata finito los estados finales están encerrados
en un círculo doble.
Cuando se usa un autómata para detectar secuencias, también se lo conoce con el
nombre de máquina de estado finito reconocedora o detectora de secuencia. Este tipo de
sistema suele tener una salida cuya única función es la de indicar que se ha alcanzado el
estado de éxito, de manera que un agente externo a la máquina podría reconocer que se ha
reconocido la secuencia, una vez se active la salida.
Las Máquinas de Estado Finito son útiles para reconocer contraseñas, códigos o la
validación de paquetes de datos en transmisión digital.
�
Ejemplo 10.5 — Máquina de Estado Finito detectora. Determine cuál es la secuencia
de cuatro dígitos que detecta la máquina de estados de la figura 10.9 sabiendo que las
entradas al sistema son números en base tres y que la salida se pone en ‘1’ sólo cuando se
ingresa la secuencia correcta.
Figura 10.9: Diagrama de Estados de una máquina detectora de secuencias
La máquina inicia en el estado de reposo s0 . Hay dos posibles rutas y dos posibles
estados finales s4 y s8 . Podríamos asumir que la ruta hacia el estado s4 es la ruta que detecta
la secuencia correcta pues la salida en la transición hacia ese estado es ‘1’ lo que haría de
la otra ruta, el desvío para la secuencia incorrecta.
Capítulo 10. Máquinas de Estado Finito
36
Analizando la ruta correcta se tiene que la secuencia que se busca detectar es “0112”.
Como la salida solo es ‘1’ en la transición hacia el estado final s4 y como la secuencia
detectada está en base 3, podemos asegurar que esta ruta es, ciertamente, la que detecta la
secuencia correcta.
�
La detección de secuencias se puede hacer de dos formas. Supongamos que queremos
detectar la secuencia binaria "101101"dentro de la secuencia "101011011011101101".
Podríamos analizar (dividir) el patrón por bloques de seis bits (dado que la longitud de la
clave “101101” es 6) y encontraríamos la clave una sola vez:
101011 − 011011 − 101101
Este análisis parece ser como una carga “paralela” (aunque no lo sea) pues parece que
hemos cargado bloques de 6 bits, para luego analizarlos. Si, en cambio, analizáramos el patrón “a medida que va llegando” (lo cual parecería ser una carga en “serie”) encontraríamos
dos veces la clave:
10 − 101101 − 101110 − 1101
El primer método se conoce como máquina de estado finito detectora sin solapamiento
mientras que el segundo método se conoce como máquina de estado finito detectora con
solapamiento.
Definición 10.3.2 — Solapamiento de secuencias. Una secuencia s0 = x1 x2 ...xr−1 xr ,
de longitud r, se solapa con otra secuencia s1 = y1 y2 ...y p−1 y p , de longitud p ≥ r, cuando
se puede formar una secuencia s2 = z1 z2 ...zk−1 zk = xr−k+l+1 xr−k+l+2 ...xr y1 y2 ...yl−1 yl ,
de longitud k, con los últimos k − l ≤ r elementos de s0 y los primeros l ≤ p elementos
de s1 .
10.3.1
Máquina de Estado Finito Detectora SIN Solapamiento
En ciertos casos, es necesario detectar que una secuencia se ha introducido de forma
errónea. Por ejemplo, supongamos el siguiente escenario:
El día de ayer me quedé sin dinero para salir con mi novia así que fui al cajero para
retirar solo el 10 % del saldo de mi cuenta. La clave de mi tarjeta débido es 1231. Introduje
mi tarjeta en el cajero, retiré mi dinero y me fui tranquilo. La persona que me seguía en la
cola también iba a retirar plata. La clave de la tarjeta débido de esta persona era 2314. A
simple vista se puede ver que ambas claves son distintas.
Por desgracia, el ingeniero que diseñó ese cajero, lo hizo con una máquina de estado
finito detectora con solapamiento y cuando yo metí mi clave, la máquina quedó con la
secuencia “1231” almacenada. Cuando quien me seguía introdujo la clave “2314”, este ya
tenía parte de la mía (1231), solapándose antes de que digitara el último dígito de la suya
(1231 − 2314).
Al escribir solamente 231 ya había conseguido acceso a mi cuenta bancaria y pudo
retirar, por desgracia, el 90 % de mi saldo restante.
Este es un ejemplo de los casos en que no es deseable tener una detectora con solapamiento. No obstante, esto no implica que en ningún caso se desee tener una máquina de
este tipo. Más adelante veremos las máquinas con solapamiento.
10.3 Autómata finito
37
Diseño de una Detectora SIN solapamiento
En el diseño una detectora sin solapamiento debemos tener por lo menos dos rutas con
estados finales que requieran reinicio: una que corresponda a la secuencia correcta y otra
que corresponda a cualquier posible secuencia errónea. Ya habíamos visto un ejemplo de
este tipo de detectoras en la figura 10.9.
Para diseñar la ruta “correcta”, crearemos un estado por cada uno de los dígitos de la
secuencia que se deba comprobar. En la transición hacia el último dígito (estado) se debe
indicar que la salida fue correcta, haciendo uso de las salidas de la máquina. En la figura
10.10 se muestra un ejemplo de esta construcción.
Figura 10.10: Detectora de secuencias sin solapamiento para la secuencia “101”
A la hora de diseñar la ruta “errónea” hay que distinguir el propósito de la máquina
detectora de secuencias, pues la máquina podría ser diseñada para optimizar cómputo o
bien para validar claves. Veremos un ejemplo de ambos casos:
�
Ejemplo 10.6 — Detectora sin solapamiento para optimizar código. Doña Juana,
la señora que vende tintos en Digita-landia, se siente desconsolada. Alguien cometió un
crimen gravísimo en contra de ella: le robó un cubo de azúcar. Doña Juana no sabe quién es
el culpable en una ciudad de 8 habitantes: solo tiene una gota de sangre que quedó en la caja
de azúcar. La Universidad de Antioquia encontró que la cadena de ADN del sospechoso es:
“101” así que basta con comparar esta cadena, con la de los 8 habitantes de Digita-landia.
Aunque parece ser una tarea muy fácil, sólo se dispone de un computador que efectúa una
operación por minuto, por lo que sería muy bueno si se pudiera disminuir el tiempo de
computo. Modele el sistema como una máquina de estados finito sin solapamiento.
Para empezar, es crucial saber que las secuencias no se pueden solapar porque si así
fuera, se incriminaría al sospechoso incorrecto. Ahora, vamos a diseñar la máquina de
manera que logremos identificar cuándo la secuencia deja de coincidir. La máquina de
estados tendrá tres posibles salidas: una para saber que la máquina está procesando, otra
para saber que el procesamiento terminó sin éxito y otra para saber que el procesamiento
terminó exitosamente. Las salidas serán: “00”, “01” y “10”, respectivamente.
38
Capítulo 10. Máquinas de Estado Finito
En la figura 10.11 se muestra la ruta “correcta” de la máquina.
Figura 10.11: Ruta correcta del identificador de ADN “101”
Si al sistema entra un dígito erróneo, deberá salir inmediatamente, para que se compare
una nueva secuencia lo más pronto posible. En la figura 10.12 se muestra el diagrama
completo.
Figura 10.12: Diagrama completo del identificador de ADN “101”
�
Ejercicio 10.2 Analice los tiempos de cómputo al comparar la secuencia “101” contra
todas las posibles secuencias de 3 bits, usando el diagrama de la figura 10.12 y el
10.3 Autómata finito
39
diagrama de la figura 10.13. ¿Cuál requiere menos tiempo para hacer los cálculos si
ambas máquinas efectúan una operación por minuto?
Figura 10.13: Diagrama del identificador de ADN “101” NO óptimo
�
Ejercicio 10.3 — Búsqueda de un criminal. Después de encontrar al ladrón de cubos
de azúcar, se lo acusa también de robar tres bolsitas de sal en la ciudad vecina de Digitalandia en el año de 1994. Su cédula es “1230567” y presuntamente debería encontrarse
en una lista de 107 personas (todas las cédulas tienen 7 dígitos). Diseñe una máquina de
estado finito sin solapamiento para hallar la cédula del criminal.
�
Ejemplo 10.7 — Detectora sin solapamiento para validar contraseñas. Para poder
retirar dinero de su cuenta bancaria, deberá proporcionar la clave “101” al cajero. Modele
el sistema como una máquina de estados finito sin solapamiento. Asuma que las salidas
de la máquina son “00”para indicar que la máquina está procesando, “01” para indicar
que el procesamiento terminó y la contraseña es incorrecta y “10” para indicar que el
procesamiento terminó exitosamente.
En este ejemplo no se puede diseñar una máquina que optimice el tiempo. Suponga el
siguiente escenario: Javier es un ladrón novato que se acabó de encontrar una tarjeta débito
al lado del cajero, cuya clave es “101”. El cajero tiene entrada binaria y fue diseñado como
una máquina de estados detectora sin solapamiento para optimizar código igual a aquella
de la figura 10.12. El cajero llama a la policía cuando la clave de una cuenta se ingresa 3
veces de forma incorrecta.
Javier entra a él y trata de descubrir la contraseña de la cuenta:
Primero ingresa un ‘0’. El cajero interrumpe inmediatamente la transacción (la salida
de la máquina fue “01”), por lo que Javier ya sabe que el primer dígito es ‘1’. Volverá a
intentarlo: esta vez, empieza ingresando un ‘1’ y luego ingresa otro ‘0’. Esta vez el cajero
no finalizó la transacción porque era justamente este dígito el que seguía en la secuencia.
�
40
Capítulo 10. Máquinas de Estado Finito
Ahora Javier va por el último: ingresa otro ‘0’ y el cajero detiene la transacción. Javier ya
sabe que la clave de la tarjeta es “101” y todavía no se ha activado la alarma.
En este tipo de escenarios NO se puede usar una detectora optimizadora de código. Se
debe hacer que la ruta “errónea” sea tan larga como la ruta “correcta” para que quien use la
máquina no se entere (con tanta facilidad) de la secuencia válida. La máquina que modela
el funcionamiento del cajero se muestra en la figura 10.14.
Figura 10.14: Diagrama del cajero que detecta la clave “101”
Analicemos la figura 10.14 en el mismo escenario anterior: Javier llega e introduce
un ‘0’. La máquina sigue por la ruta errónea pero no finaliza la transacción. Javier supone
que el primer dígito fue correcto así que introduce otro ‘0’. La máquina sigue por la ruta
errónea (aunque este segundo dígito sí sea correcto, una vez en s4 , no importa cuál sea
la entrada, la máquina continuará en la ruta errónea) y todavía no finaliza la transacción.
Finalmente, Javier introduce un último ‘0’ con lo que la máquina finaliza la transacción
(la salida fue “01”). Javier supone que el error estuvo en el último dígito así que vuelve
a intentar, pero con la secuencia “001”. La máquina finaliza nuevamente la transacción.
Javier, desconcertado, vuelve a intentar, pero ahora empieza con un ‘1’. La máquina pasa
al estado s1 que hace parte de la ruta correcta. Ahora Javier introduce otro ‘1’ (la máquina
salta a la ruta errónea) e ingresa un último ‘1’. Aunque el primer y último dígitos sean
correctos, la máquina solo finaliza la transacción después del último de ellos. Javier vuelve
a intentarlo, pero ya es demasiado tarde pues unos 20 policías del Cuerpo Policial de
Digita-landia lo tienen rodeado.
�
Con los ejemplos 10.6 y 10.7 se quiso mostrar los dos tipos de máquinas de estado finito
detectoras de secuencia sin solapamiento. Analice muy bien para qué tipo de escenario se
usa cada una de ellas.
10.3.2
Máquina de Estado Finito Detectora CON Solapamiento
Los ejemplos anteriores mostraban que existen casos en los que no es deseable tener
una detectora con solapamiento. No obstante, esto no implica que en ningún caso se desee
10.3 Autómata finito
41
tener una máquina de este tipo. Supongamos, ahora el siguiente escenario:
Recién han contratado a Gloria para que se encargue de la seguridad informática del
Banco de la República. Resulta que en los últimos días ha circulado por toda la internet un
nuevo virus con un identificador binario “11001110”. Su tarea es identificar los paquetes
que tengan dicho identificador.
Ella abrió su analizador de paquetes para inspeccionar todo el tráfico que entraba al
banco y recibió una cadena muy sospechosa: “111110001001110011101111”. Si usara
una detectora sin solapamiento debería separar la secuencia en grupos de 8 bits:
111110001001110011101111
11111000 − 10011100 − 11101111
Parecería que el identificador del virus no está presente en la secuencia, sin embargo,
si analizamos la secuencia con solapamiento tenemos que:
111110001001110011101111
111110001001 − 11001110 − 1111
Por lo que sí ha llegado el identificador del virus. El truco aquí consiste en reconocer
que, hasta donde se ha analizado la cadena, aunque no se haya encontrado la clave completa,
hay algunos dígitos que nos sirven para formarla. Primero, como ya debe ser costumbre,
se prepara la ruta “correcta”, la cual es mostrada en la figura 10.15.
Figura 10.15: Ruta correcta del diagrama con solapamiento para hallar la secuencia
“11001110”
42
Capítulo 10. Máquinas de Estado Finito
Para construir la ruta “incorrecta”, tenemos que analizar la secuencia acumulada a
medida que añadimos entradas incorrectas a ruta “correcta”. Veamos:
1. En s0 no tenemos valores acumulados de la secuencia “correcta” así que si llega un
‘0’, seguiremos sin tener valores acumulados de la secuencia. Por esta razón, estando
en s0 , si llega un ‘0’, seguiremos en s0 .
2. En s1 tenemos acumulada la secuencia “1” (un único dígito). Si llega un ‘0’, se
tendrá acumulada la secuencia “10” la cual no hace parte1 de la secuencia “correcta”.
De esta manera, estando en s1 , si llega un ‘0’, iremos a s0 .
3. En s2 tenemos acumulada la secuencia “11”. Si llega un ‘1’, tendremos acumulada
la secuencia “111”. De esta secuencia nos sirven los últimos dos dígitos: “11”. De
esta manera, estando en s2 , si llega un ‘1’, seguiremos en s2 .
4. En s3 tenemos acumulada la secuencia “110”. Si llega un ‘1’, tendremos acumulada
la secuencia “1101”. De esta secuencia no podemos formar parte de la secuencia
correcta. De esta manera, estando en s3 , si llega un ‘1’, iremos a s0 .
5. En s4 tenemos acumulada la secuencia “1100”. Si llega un ‘0’, tendremos acumulada
la secuencia “11000”. De esta secuencia no podemos formar parte de la secuencia
correcta. De esta manera, estando en s4 , si llega un ‘0’, iremos a s0 .
6. En s5 tenemos acumulada la secuencia “11001”. Si llega un ‘0’, tendremos acumulada la secuencia “110010”. De esta secuencia, tampoco podemos formar parte de la
secuencia correcta. De esta manera, estando en s5 , si llega un ‘0’, iremos a s0 .
7. En s6 tenemos acumulada la secuencia “110011”. Si llega un ‘0’, tendremos acumulada la secuencia “1100110”. De esta secuencia nos sirven los últimos tres dígitos:
“110”. De esta manera, estando en s6 , si llega un ‘0’, iremos a s3 que es en donde se
tiene acumulada la secuencia “110”.
8. En s7 tenemos acumulada la secuencia “1100111”. Si llega un ‘1’, tendremos
acumulada la secuencia “11001111”. De esta secuencia nos sirven los últimos
dos dígitos: “11”. De esta manera, estando en s7 , si llega un ‘1’, iremos a s2 que es
en donde se tiene acumulada la secuencia “11”.
9. s8 es un estado especial: aunque en este estado se tiene acumulada la secuencia
“11001110” debemos borrar lo que tenemos acumulado. Así, si llega un ‘0’, iremos a s0 (que es donde acumulamos ‘0’s) y si llega un ‘1’, iremos a s1 (que es donde
tenemos acumulado solo un ‘1’).
Supongamos que la secuencia que debíamos detectar hubiera sido “111001110” y que
no “borramos” lo que teníamos acumulado. Si en el estado final llegase un ‘0’ deberíamos
ir (aunque no sea correcto) al estado que tenga acumulado “11100”. Después de ingresar
la secuencia “1110” habríamos completado dos veces la clave (la salida se pondría dos
veces en alto) pero, ¿qué secuencia introdujimos hasta ahora? La secuencia que usamos
fue “111001110011100” y allí NO hay dos secuencias “111001110”. Por eso hay que tener
mucho cuidado de borrar lo que tenemos acumulado una vez alcanzamos el estado final.
En la figura 10.16 se muestra el diagrama de estados final para detectar la secuencia
111001110 con solapamiento.
1 En base a la definición 10.3.2 habrá solapamiento si en los últimos “n” dígitos de la secuencia acumulada,
tenemos los “n” primeros dígitos de la secuencia correcta
10.4 Máquina de Estados tipo Moore
43
Figura 10.16: Diagrama con solapamiento para hallar la secuencia “11001110”
Ejercicio 10.4 — Compilador de C. Cuando el compilador de C encuentra la se-
cuencia #include en un código, debe incluir la librería que se encuentre después del
identificador. Modele este escenario con una máquina de estados finitos teniendo en
cuenta que cada caracter imprimible se puede representar con un número decimal de la
tabla ASCII.
�
10.4
Máquina de Estados tipo Moore
Note que hasta el momento siempre hemos puesto la salida de la máquina de estado en
la transición de un estado s a un estado s� .
Cuando TODAS las transiciones hacia un estado s� tienen la misma salida o� , podríamos,
en vez de poner la salida en la transición, ponerla en el estado; así, en vez de dibujar las
transiciones de estado como en la figura 10.17 podríamos hacerlo como se muestra en la
figura 10.18.
Capítulo 10. Máquinas de Estado Finito
44
Figura 10.17: Conexión entre dos estados tipo Moore
Figura 10.18: Conexión entre dos estados tipo Moore
En la figura 10.18 no solo se puede ver que todas las transiciones hacia s� tienen la
salida o� sino, también, que todas las transiciones hacia s tienen la salida o. Cuando todos
los estados se pueden expresar con esta notación, se denomina a esta máquina como
Máquina de Estado Finito tipo Moore y se podrá usar la notación de la figura 10.18. Si al
menos un estado no se puede expresar de esta forma, se tendrán que poner las salidas en
todas las transiciones. A este tipo de máquina se la denomina Máquina de Estado Finito
tipo Mealy y se tendrá que usar la notación de la figura 10.17.
10.5
Eliminación de Estados Redundantes
Sección tomada del libro de Taub
Los estados de una Máquina de Estado Finito nos permiten memorizar información
relevante del sistema. Algunas veces, mientras diseñamos nuestra máquina, veremos que
nos harán falta estados para que funcione el sistema. Otras veces, añadiremos estados
irrelevantes pensando en que ha aparecido nueva información. Estos estados en los que no
se memoriza nueva información se denominan estados redundantes.
Puede ser que la máquina funcione a la perfección con los estados redundantes y puede
ser, también, que en el papel no haya problema en añadir tantos de estos estados como
queramos; pero, una cosa es el papel y otra cosa muy distinta es la vida real. Cuando
queremos llevar nuestro diseño a una implementación circuital discreta, necesitamos
reducir el número de estados al mínimo pues, de no hacerlo, incrementaríamos el tiempo
de funcionamiento de nuestra máquina, los costos del diseño, consumo de energía, espacio,
temperatura, entre muchos otros problemas más. Es por esto que debemos procurar tener
una máquina de estados con la menor cantidad de estados posibles.
Lo importante a tener en cuenta al tratar con estados redundantes es que un sistema
secuencial se construye con el único propósito de obtener una secuencia determinada
de niveles lógicos de la salida o salidas en respuesta a la secuencia o secuencias de
entrada(s). Así pues, supongamos dos sistemas secuenciales. Uno con 20 estados y otro
con 2 estados. Supongamos finalmente que ambos sistemas dan las mismas secuencias
de salida para las mismas secuencias arbitrarias de entrada. Entonces, en lo que nos
concierne, los dos sistemas son idénticos e indistinguibles. El sistema de 20 estados tiene
la potencialidad de suministrar salidas que el sistema de dos no puede. Sin embargo, hasta
que no aprovechemos la potencialidad, los sitemas serán indistinguibles. Por tanto, bajo
estas circunstancias consideramos reundantes 18 de los 20 estados del primer sistema.
10.5 Eliminación de Estados Redundantes
45
Existen varias técnicas para eliminar estados redundantes. Mencionaremos la eliminación por simple inspección y por partición. Existe otra técnica más, que funciona mejor que
las dos que trataremos a continuación, pero que para el alcance y problemas del curso no
es necesario que veamos. Aún así, si quiere revisarla, la podrá encontrar en los ejemplos de
los capítulos 7.17 y 7.18 del libro de Taub que aparece en las referencias de este capítulo.
10.5.1
Eliminación por Simple Inspección
Consideremos la situación representada en la tabla de estados de la tabla 10.9. Contemplamos un sistema Mealy con una sola entrada X y una única salida Z (el método
también es válido para un sistema Moore con n > 1 entradas y m > 1 salidas). No se
ha especificado la tabla completa de estados; pero prestaremos atención al hecho de que
en la tabla aparecen dos estados especiales p y q tales que si el estado presente es p o
q, independientemente del valor de X, las salidas son idénticas y los estados siguientes
también. Es decir, encontramos dos estados p y q en la columna estado actual cuya salida
actual Z y estados siguientes coinciden. Entonces, claramente se intuye que estos estados
son indistinguibles y uno de ellos puede despreciarse. Si el estado actual es p o q la salida
es la misma. También si, por ejemplo, X = 0, en ambos casos el siguiente estado es r y el
futuro del sistema dependerá de r y no si de que p o q precedían a r.
S
S+ /Z
X =0
X =1
...
p
...
q
...
...
r/0
...
r/0
...
...
s/1
...
s/1
...
Cuadro 10.9: Tabla de estados donde dos estados, p y q, tienen los mismos siguientes
estados y salidas para todos los valores de X. S: Estado actual. S+ : Estado siguiente.
�
Ejemplo 10.8 La tabla 10.10 tiene estados redundantes y los eliminaremos según el
método ya explicado.
S
S+ /Z
X =0
X =1
A
B
C
D
E
B/0
C/0
D/1
C/0
D/0
C/1
A/1
B/0
A/1
C/1
Cuadro 10.10: Tabla de estados donde dos estados, B y D coinciden.
Examinando sistemáticamente las filas de esta tabla, encontramos que los estados B y
D tienen iguales el estado siguiente y las salidas. Diremos, entonces, que uno de estos dos
Capítulo 10. Máquinas de Estado Finito
46
estados es innecesario puesto que son indistinguibles. Eliminemos entonces el estado B.
(También pudimos haber eliminado a D). La tabla 10.11 es la tabla de estados reducida.
S
S+ /Z
X =0
X =1
A
C
D
E
D/0
D/1
C/0
D/0
C/1
D/0
A/1
C/1
Cuadro 10.11: Tabla de estados reducida, luego de eliminar a B.
En esta tabla de estados reducida, se ha eliminado el estado B de todos los sitios donde
aparece y es sustituido por D. Como resultado de esta operación, encontramos ahora que
los estados A y E hacen visible su equivalencia. Eliminaremos, ahora, el estado A y la
nueva tabla de estados reducida aparece en la figura 10.12, donde no son posibles más
reducciones.
S
S+ /Z
X =0
X =1
C
D
E
D/1
C/0
D/0
D/0
E/1
C/1
Cuadro 10.12: Tabla de estados más reducida, luego de eliminar a A.
�
10.5.2
Eliminación por Partición
En la sección previa vimos que en una tabla de estados, dos estados cuyos estados
siguientes eran idénticos y sus salidas también lo eran, entonces estos dos eran realmente
estados idénticos; luego uno de los estados podía ser eliminado. Ahora veremos que
una tabla de estados puede tener estados redundantes aún cuando no aparezcan filas con
idénticas salidas y los mismos estados siguientes.
Para ilustrar este punto y ver cómo se determinan los estados redundantes, analicemos
el ejemplo 10.9.
�
Ejemplo 10.9 — El niño diferente. Debemos reducir los estados redundantes de la tabla
10.13.
10.5 Eliminación de Estados Redundantes
47
S
S+ /Z
X =0
X =1
A
B
C
D
E
F
G
H
B/0
D/0
G/0
H/0
G/1
G/0
D/0
H/0
C/0
F/0
F/0
E/0
A/0
A/0
C/0
A/0
Cuadro 10.13: Tabla de estados.
Un examen de la tabla revela que no hay filas con los mismos estados e idénticas
salidas. Teniendo en cuenta que la misión de un sistema secuencial es suministrar salidas
cuando se requieran, examinemos en la tabla las salidas. Encontramos que todas las salidas
son idénticas excepto para el estado E por lo que, de alguna forma, el estado E debe ser
diferente de los demás. E es el niño diferente del grupo. Los otros estados tienen Z = 0
cuando X = 0 mientras que E mantiene Z = 1 cuando X = 0. Como todos los estados
excepto E tienen la misma salida, entonces serán el mismo estado. Diviremos la tabla
10.13 en particiones según como lo indican los subíndices de la tabla 10.14. A todos los
estados, excepto al E, los pondremos en la partición 1 y al E lo pondremos en la 2.
S
S+ /Z
X =0
X =1
A1
B1
C1
D1
E2
F1
G1
H1
B/0
D/0
G/0
H/0
G/1
G/0
D/0
H/0
C/0
F/0
F/0
E/0
A/0
A/0
C/0
A/0
Cuadro 10.14: Bautizar las particiones iniciales.
Hasta que la hipótesis se haga insostenible, supondremos que todos los estados de la
misma partición realmente son el mismo estado (porque tienen las mismas salidas). Una
vez escrita la tabla 10.14, las salidas ya no nos proporcionan más información por lo que
no es necesario volverlas a escribir, por lo que la tabla 10.14 se puede convertir en la tabla
10.15.
Capítulo 10. Máquinas de Estado Finito
48
S
X =0
A1
B1
C1
D1
E2
F1
G1
H1
S+
B1
D1
G1
H1
G1
G1
D1
H1
X =1
C1
F1
F1
E2
A1
A1
C1
A1
Cuadro 10.15: Eliminar las salidas, pues estas ya no proporcionan información para la
reducción
Ahora, al analizar la tabla 10.15 encontramos que el estado D, que inicialmente estaba
en la partición 1, realmente no puede ser el mismo estado que los demás estados de la
partición 1 puesto que cuando X = 1, todos los demás estados de la partición 1 van a
estados de partición 1 mientras que D va al estado E, el cual pertenece a una partición
diferente. En principio, cuando dos estados cuyos estados siguientes en la columna de
estado siguiente no pertenecen a la misma partición deben ser estados diferentes, por
lo que D no puede pertenecer a la misma partición que A, B, C, F, G y H; así que lo
pondremos en la partición 3 como se muestra en la tabla 10.16. También hemos de corregir
los subíndices de los estados siguientes de B y G.
S
X =0
A1
B1
C1
D3
E2
F1
G1
H1
B1
D3
G1
H1
G1
G1
D3
H1
S+
X =1
C1
F1
F1
E2
A1
A1
C1
A1
Cuadro 10.16: Etapa 1 en la reducción de la tabla de estados.
Empleando el principio anterior, encontramos ahora en la tabla 10.16 que los estados B
y G no pueden permanecer en la partición 1. Estos dos estados van a estados en la columna
de estado siguiente que están en la misma partición. Es decir, cuando X = 0, tanto B como
G van a estados de la partición 3 y cuando X = 1, tanto B como G van a estados de la
partición 1. Es por esto que los retiraremos de la partición 1 y los colocaremos juntos en
una nueva partición (4) tal y como se indica en la figura 10.17.
10.5 Eliminación de Estados Redundantes
S
X =0
A1
B4
C1
D3
E2
F1
G4
H1
S+
B4
D3
G4
H1
G4
G4
D3
H1
49
X =1
C1
F1
F1
E2
A1
A1
C1
A1
Cuadro 10.17: Etapa 2 en la reducción de la tabla de estados.
En la tabla 10.17 encontramos que los estados A, C y F no pueden compartir la misma
partición con H, así que los pondremos juntos2 en una nueva partición (5) como se muestra
en la figura 10.18.
S
X =0
A5
B4
C5
D3
E2
F5
G4
H1
B4
D3
G4
H1
G4
G4
D3
H1
S+
X =1
C5
F5
F5
E2
A5
A5
C5
A1
Cuadro 10.18: Etapa 3 en la reducción de la tabla de estados.
Al comparar todos los estados, vemos que en la tabla 10.18 no son necesarias más
particiones. En este punto, todos los estados que están en la misma partición (A, C y F en
la partición 5 y B y G en la partición 4) tienen en cada columna de siguiente estado, una
transición hacia algún estado de una misma partición.
Cuando la partición es completa, todos los estados en la misma partición son el mismo
estado. Como tenemos 5 particiones, tendremos solo cinco estados. Usaremos letras
minúsculas para etiquetas estos estados: a = (A,C, F), b = (B, G), c = D, d = E y e = H.
En la tabla se muestra la tabla reducida.
2 Ya
vimos que pueden ir juntos pues dada la entrada X = 0 todos irán hacia algún estado de la misma
partición (4) y dada la entrada X = 1 todos irán hacia algún estado de la misma partición (1).
Capítulo 10. Máquinas de Estado Finito
50
S
S+ /Z
X =0
X =1
a
b
c
d
e
b/0
c/0
e/0
b/1
e/0
a/0
a/0
d/0
a/0
a/0
Cuadro 10.19: Tabla de estados reducida.
La tabla reducida la formamos en el orden que aparecen las letras a, b, c, d y e,
obviamente, en base a las transiciones de estado (particiones) de la tabla 10.18 y las salidas
de los estados de la tabla 10.13. Empecemos por a: cualquier estado de esta partición,
a = (A,C, F), cambiará a un estado de la partición b = (B, G) cuando X = 0 con una salida
Z = 0; mientras que, cuando X = 1, cambiará a un estado de la partición a = (A,C, F) con
salida Z = 0. Ahora, analicemos el estado b:cualquier estado de esta partición, b = (B, G),
cambiará a la partición c = D cuando X = 0 con una salida Z = 0; mientras que, cuando
X = 1, cambiará a un estado de la partición a = (A,C, F) con salida Z = 0. Se puede
comprobar fácilmente el resto de los estados.
�
10.6
Circuitos de Moore y de Mealy
Ya vimos toda la teoría sobre Máquinas de Estado Finito. Lo que resta, ahora, es
implementar las máquinas que ya sabemos diseñar con circuitos secuenciales.
En el capítulo 9 se estudió el proceso de diseño general de los circuitos secuenciales.
Así que, en principio, este método debería servirnos para la implementación de cualquier
Máquina de Estado Finito. No obstante, el procedimiento expuesto estaba enfocado al
diseño de contadores síncronos por lo que haremos algunas modificaciones a este método a
medida que diseñamos una Máquina de Estado Finito tipo Mealy que detecte la secuencia
sin solapamiento: 1011. Consideremos que la salida de la máquina es 00 mientras está
procesando la cadena, 01 si consigue un análisis exitoso y 10 si el análisis falla.
10.6.1
Diagrama de Estados
Nosotros ya somos capaces de crear el diagrama de estados para el sistema pedido.
Primero, diseñamos la ruta correcta como se muestra en la figura 10.19. En ella debe haber
cabida para cada uno de los bits que hacen parte de la secuencia clave.
10.6 Circuitos de Moore y de Mealy
51
Figura 10.19: Ruta correcta
Luego, asumiendo que se busca hacer una máquina para “optimizar cómputo” se añade
la ruta errónea al diagrama en la figura 10.20.
Figura 10.20: Diagrama de Estados Final
El diagrama de estados de la figura 10.20 es el de una máquina tipo Mealy. Bien podríamos hacerlo tipo Moore pero, por ahora, concentrémonos únicamente en las máquinas
tipo Mealy.
10.6.2
Tabla de Transición de Estados
El siguiente paso consiste en representar el diagrama de estados con una tabla de
transición de estados como se muestra en la tabla 10.20.
En esta tabla hemos puesto que, como S4 y S5 son estados finales, permanecerán allí
sin importar el valor de la entrada.
Capítulo 10. Máquinas de Estado Finito
52
Estado actual
S
Estado Siguiente
S+ /Z
X =0
X =1
S0
S1
S2
S3
S4
S5
S5 /10
S2 /00
S5 /10
S5 /10
S4 /00
S5 /00
S1 /00
S5 /10
S3 /00
S4 /01
S4 /00
S5 /00
Cuadro 10.20: Tabla de Transición de Estados para el detector de la secuencia 1011
10.6.3
Bautizar Estados en forma Digital
Como bien ya lo vimos en el capítulo 9, los estados serán representados con un conjunto
de Flip-Flops. Es por esta razón que necesitamos dar una notación binaria a cada estado
de la tabla 10.20. Puede ser cualquier notación. Por ejemplo, podríamos decir que S0 será
representado por la secuencia 000001, S1 por la secuencia 000010, S2 por la secuencia
000100, S3 por la secuencia 001000 y así sucesivamente. También podríamos representar
los estados como: S0 = 000, S1 = 001, S2 = 010, S3 = 011 y así sucesivamente. Existen
incontables maneras de representar los estados con una notación binaria, lo importante
es saber que se usará determinada notación binaria dependiendo de las condiciones del
sistema. Por ejemplo, si el sistema para el cual diseñamos la máquina de estados sólo
acepta entradas one-hot3 entonces usaríamos la primera representación mencionada. Si, en
cambio, estamos escasos de recursos usaríamos la segunda notación.
En este ejemplo, bautizaremos los estados buscando la mínima implementación. Es
de notar que este diagrama de estados tiene 6 estados. Si quisiéramos obtener la mínima
implementación tendríamos que considera que con 2 Flip-Flops solo podríamos representar
4 estados (22 combinaciones) mientras que con 3 Flip-Flops podríamos representar 8
estados (23 combinaciones) por lo que usaremos 3 Flip-Flops y convertiremos la tabla
10.20 en la tabla 10.21
Estado actual
Q2
Q1
Q0
Q2+
X =0
Q1+ Q0+
0
0
0
0
1
1
0
0
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
0
1
0
0
0
0
1
0
1
1
0
1
Estado Siguiente
Z
Q2+
X =1
Q1+ Q0+
Z
10
00
10
10
00
00
0
1
0
1
1
1
0
0
1
0
0
0
00
10
00
01
00
00
1
1
1
0
0
1
Cuadro 10.21: Tabla transición de estados digital.
3 La codificación one-hot consiste en tener una palabra de n bits donde sólo un bit puede estar en alto
mientras que los demás estarán en nivel bajo. Aquella codificación en que todos los bits son ‘1’ excepto uno
que será ‘0’ se denomina one-cold.
10.6 Circuitos de Moore y de Mealy
53
Para hacer el cambio de la tabla 10.20 a la tabla 10.21 hemos tomado S0 = 000,
S1 = 001, S2 = 010, S3 = 011, S4 = 100 y S5 = 101.
10.6.4
Tablas de Transición de los Flip-Flops
Después de determinar el número de flip-flops necesarios para llevar a cabo la implementación, necesitamos definir el tipo (o tipos) de flip-flop(s) que se usará, para luego
determinar las funciones lógicas combinaciones de sus respectivas entradas. Hay que tener
presente que se necesitarán tantos flip-flops como bits para representar los estados de la
máquina.
En este ejemplo tenemos estados de 3 bits por lo que se necesitarán 3 flip-flops.
Asumamos que este ejemplo se debe implementar únicamente con flip-flops tipo J − K.
Como necesitamos 3 flip-flops, tendremos que definir 8 funciones combinacionales para
todo el sistema (una por cada entrada de los 3 flip-flops J-K, más dos salidas). Para ello,
haremos las tablas de verdad para las entradas Ji y Ki (i = 0, 1, 2) en base a la tabla de
transiciones para un flip-flop J-K mostrada en la figura 10.22.
Transiciones de salida
Q Q+
Entradas del Flip-Flop
J K
0
0
1
1
0
1
X
X
0
1
0
1
X
X
1
0
Cuadro 10.22: Tabla de transiciones para un flip-flop J-K
Podemos convertir la tabla 10.21 la tabla 10.23.
10.6.5
Obtención de las expresiones lógicas
Mediante cualquier método de minimización de expresiones lógicas, obtendremos las
expresiones lógicas para Z0 y Z1 , J0 y K0 , J1 y K1 y J2 y K2 .
El procedimiento para hallar la expresiones lógicas ya es bien conocido y por eso
se omitirá. En caso de no entender el cómo, revise los capítulos 2 y 3. Las funciones
combinacionales que requerimos son:
Z0 = Xin · Q1 · Q0
(10.1)
Z1 = Xin · Q2 · Q1 + Xin · Q1 + Xin · Q2 · Q1 · Q0
(10.2)
J0 = Q2
(10.3)
K0 = Xin · Q2 · Q1 + Xin · Q1
(10.4)
K1 = Xin + Q2 · Q0
(10.6)
J1 = Xin · Q2 · Q0
(10.5)
J2 = Xin · Q0 + Xin · Q1 + Xin · Q0 = Xin ⊕ Q0 + Xin · Q1
K2 = 0
(10.7)
(10.8)
Capítulo 10. Máquinas de Estado Finito
54
Estado Actual
Xin Q2 Q1 Q0
Siguiente estado
Q2+ Q1+ Q0+
Salidas
Z1 Z0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
X
X
0
1
0
1
1
1
X
X
1
0
1
1
0
0
X
X
0
1
0
0
0
0
X
X
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
X
X
0
0
1
0
0
0
X
X
1
0
1
1
0
1
X
X
1
1
1
0
0
1
X
X
0
0
0
0
0
0
X
X
0
0
0
1
0
0
X
X
J2
Entradas Mínimas
K2
J1 K1
J0
K0
1
0
1
1
X
X
X
X
0
1
0
1
X
X
X
X
X
X
X
X
0
0
X
X
X
X
X
X
0
0
X
X
X
1
X
0
X
0
X
X
X
0
X
1
X
0
X
X
0
1
X
X
0
0
X
X
0
0
X
X
0
0
X
X
X
X
1
1
X
X
X
X
X
X
0
1
X
X
X
X
1
X
1
X
0
X
X
X
1
X
1
X
0
X
X
X
Cuadro 10.23: Tabla del siguiente estado de los flip-flops. Xin es la entrada de la MEF,
mientras que X es un estado irrelevante.
10.6.6
Implementación de la Máquina de Estados
El paso final consiste en implementar la lógica combinacional a partir de las expresiones
encontradas de las entradas J y K, y para la salida Z. El circuito final se presenta en las
figuras 10.21 y 10.22. Las dos figuras no aparecen integradas sólo para que fuera fácil
analizar el circuito.
Figura 10.21: Implementación circuital de la Máquina Detectora
Nota
Tenga muy en cuenta que la salida en este circuito puede cambiar en cualquier instante
de tiempo (no es síncrona). Por ejemplo, suponga que la máquina está en el estado S0
con entrada X = 0. En estas condiciones, la salida de la máquina será Z = 10. Si, antes
10.6 Circuitos de Moore y de Mealy
55
Figura 10.22: Salidas de la Máquina Detectora
de que cambie de estado, la entrada cambia a X = 1, la salida cambiará a Z = 00. Pero, si
justo antes de que cambie de estado, la entrada vuelve a ser X = 0, la salida volverá a ser
Z = 10.
Cuando durante el diseño de la máquina se estipuló que la salida estaba en la transición,
quiere decir que solo tomaremos la salida justo en el instante en que la máquina pasa de
un estado hacia otro. No obstante, en un diagrama de tiempos, tendríamos que dibujar la
salida asíncrona en todo momento.
Ejercicio 10.5 Diseñe una Máquina de Estado Finito tipo Moore que detecte la se-
cuencia sin solapamiento: 1011. Considere que la salida de la máquina es 00 mientras
está procesando la cadena, 01 si consigue un análisis exitoso y 10 si el análisis falla.
Compare el comportamiento de la salida de la máquina de estados tipo Moore con la
salida de la máquina tipo Mealy. ¿La máquina tipo Moore tiene salidas síncronas o
asíncronas?
�
Problemas
Problema 10.1 Diseñe un contador síncrono de 0 a 7, ascendente / descendente utilizando
FF tipo JK.
Problema 10.2 Realice el diagrama de estados, Moore y Mealy, para el detector de
secuencia 101 con solapamiento.
Problema 10.3 Repita el problema anterior, pero ahora detecte la secuencia sin solapamiento.
Problema 10.4 Realice el diagrama de estados, Moore y Mealy, para el detector de
secuencia 111 con solapamiento.
Problema 10.5 Repita el problema anterior, pero ahora detecte la secuencia sin solapamiento.
Problema 10.6 Realice el diagrama de estados, Moore y Mealy, para el detector de
secuencia 1101 sin solapamiento.
Problema 10.7 Repita el problema anterior, pero ahora detecte la secuencia sin solapamiento.
Capítulo 10. Máquinas de Estado Finito
56
Problema 10.8 Diseñe una máquina de estados que genere el complemento a uno de una
secuencia binaria cualquiera.
Problema 10.9 Añada una unidad de retraso al problema anterior.
Problema 10.10 Añada dos unidades de retraso al problema 10.8.
Problema 10.11 Diseñe un sumador en serie de dos bits.
Problema 10.12 Diseñe un sumador en serie de tres bits.
Problema 10.13 Modele el comportamiento de un ascensor como una máquina de estado
finito. Considere que el usuario solo puede manipular dos botones: arriba y abajo, que cada
movimieto es de solo un piso y que no hay llamados externos al ascensor.
Problema 10.14 Modele el comportamiento de un ascensor como una máquina de estado
finito. Considere el usuario puede ir tanto hacia arriba como hacia abajo, recorriendo varios
pisos en un solo viaje. Considere también que en el edificio en el cual funciona el ascensor
hay P pisos y que otros usuarios pueden hacer llamados externos al ascensor.
Problema 10.15 Modele el comportamiento de un semáforo como una máquina de estado
finito. El semáforo estará en rojo por 10 segundos, en amarillo por 2 segundos y en verde
por 16 segundos. De verde salta a rojo, pasando primero por amarillo. De rojo pasa a verde
sin pasar por amarillo. En cualquier momento un peatón puede pulsar un botón que le
permita cruzar la calle más rápidamente: si está en verde, permanecerá allí por 4 segundos
más y luego saltará a rojo, pasando por amarillo.
Problema 10.16 Cuando el compilador de C encuentra la secuencia #define en un código,
debe definir como constante, el valor que se encuentre después del identificador. Modele
este escenario con una máquina de estados finitos teniendo en cuenta que cada caracter
imprimible se puede representar con un número decimal de la tabla ASCII.
Problema 10.17 Modele la siguiente máquina contestadora con una Máquina de Estado
Finito tipo Mealy: Cuando llega una llamada, el teléfono suena. Si el teléfono no se levanta
en el tercer repique, la máquina contestadora se activa reproduciendo un saludo pregrabado
solicitando que la persona que llama deje un mensaje. Luego, graba 30 segundos del
mensaje de la persona que llama. Finalmente, cuelga. Si el teléfono se contesta antes del
tercer repique, la máquina contestadora no hace nada.
Referencias
Máquinas de estado finito y expresiones regulares. Matemática Discreta. Área de
Álgebra. Universidad de Coruña.
Taub, H. (1984). Circuitos digitales y microprocesadores. McGraw-Hill Interamericana de España.
Introducción a las Máquinas de Estado Finito. Álvarez, Raúl.
http://tecbolivia.com/index.php/articulos-y-tutoriales-microcontroladores/13introduccion-a-las-maquinas-de-estado-finito
Imágenes
Draw.io. https://www.draw.io/
Logicly. logic.ly/demo