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
© Copyright 2024