¿Que son las maquinas de estado finitas? - norman-ipn/Evolutivo GitHub Wiki
MÓDULO III
MÁQUINAS DE ESTADO FINITO
DESCRIPCIÓN FORMAL DE LA MÁQUINA DE ESTADO FINITO
Es un Modelo abstracto de una máquina con memoria interna primitiva. Se puede considerar a un computador como una máquina de este tipo. Una Máquina de Estado Finito M consiste en:
a) Un conjunto finito I de símbolos de entrada. b) Un conjunto finito O de símbolos de salida. c) Un conjunto finito S de estados. d) Una función estado siguiente f de S X I en S . e) Una función salida g de S X I en O . f ) Un estado inicial o , incluido en S.
Se expresa con una descripción formal como M = ( I , O , S , f, g, 0 ).
En este caso, los símbolos de entrada y salida no deben ser necesariamente diferentes, sino más bien, según sea requerido en la especificación del diseño. Nótese que se trata de símbolos, como los que se emplearon en los módulos anteriores.
DESCRIPCIÓN NO FORMAL DE LA MÁQUINA DE EDO. FINITO
Se trata de un modelo matemático, representado con recursos formales (que se especificarán posteriormente), y que puede emplearse para representar o simular el funcionamiento de un sistema real, que puede ser electrónico o computacional o de otro tipo. Ésto es muy útil, ya que posteriormente al diseño formal, se puede implementar en forma sencilla por medio de un programa escrito en cualquier lenguaje de programación.
Los sistemas que se pueden representar por medio de este modelo matemático contienen una única entrada y una sola salida, y son todos aquellos en los que no basta con conocer el valor de la entrada para conocer la salida. En este caso, existe un parámetro muy importante, llamado estado actual del sistema, y que en combinación con la entrada, ambos sí determinan una salida bien definida.
En una Máquina de Estado Finito, ocurre lo que se conoce como una Transición, una acción que consta de tres partes. Consiste en que al llegar un símbolo de entrada, el modelo responda primero con la producción de un símbolo en la salida y posteriormente (pero de manera inmediata) exista un cambio a un nuevo estado. Dicha transición es la unidad de operación en una Máquina de Estado Finito.
Es muy importante que primero se produzca la salida, antes del cambio de estado.
En este modelo se presentan dos funciones, de las mismas dos variables:
Símbolo de salida = f (estado actual, símbolo de entrada) = g. // Función g. Estado siguiente = f (estado actual, símbolo de entrada) = f. // Función f.
Veamos un ejemplo, como si la Máquina fuera una "caja negra":
En la Máquina de la figura anterior supondremos, para ejemplificar, que si la entrada es una a, y el estado actual fuese B, la salida sería un 0. Sin embargo, si el estado actual fuese D, por ejemplo, la salida podría ser 1, aún con la misma entrada a.
Se recalca que se emplea este modelo para SIMULAR todos aquellos sistemas en los que la salida no es función exclusiva de la entrada, sino también de un estado o situación actual implícita en el mismo.
EJEMPLOS SENCILLOS DE APLICACIONES DE MÁQUINAS DE ESTADO FINITO:
1 Máquina para venta de refrescos. Ya que el estado actual (cantidad de dinero que se ha depositado en ella) junto con la entrada actual (la moneda que se está depositando en cada momento) determinan la salida que el aparato entrega (nada, cambio, refresco, refresco y cambio). La misma moneda produce diferentes salidas.
2 Cajero automático. Ya que la entrada (tarjeta, NIP, botón) debe combinarse con una correcta serie de transiciones por los estados (espera usuario, espera NIP, espera requisición de servicio, etc.) para que se pueda obtener la salida deseada (billetes, impresiones de estado de cuenta, etc.). La entrada "solicito $100" en el estado "espera NIP" no produce el efectivo requerido.
3 Circuitos secuenciales digitales. Ya que en los circuitos de este tipo, es necesario conocer el potencial o voltaje que guardan ciertos puntos dentro de los mismos (es decir, los estados) para que en combinación con los valores de los bits de entrada, se conozcan los de salida. En un simple flip-flop, se requiere de conocer el estado del mismo para saber qué salida presenta.
4 Juegos de combate. Al simular una pelea, se debe considerar que las entradas (golpes, agresiones, recuperaciones) en combinación con el estado (nivel de energía del peleador) determinan el efecto que se manifestará como salida (tambalearse, caerse, cansarse, ser noqueado, etc.).
EJEMPLO: Representar la Máquina de Estado Finito de la siguiente descripción formal, por medio de un diagrama de transición y por una tabla de transición.
I = { a, b } O = { x, y, z } S = { q0, q1, q2 } 0 = { q0 }
f = { f ( q0, a ) = q1, f ( q0, b ) = q2, f ( q1, a ) = q2, f ( q1, b ) = q1, f ( q2, a ) = q0, f ( q2, b ) = q1 }
g = { g ( q0, a ) = x, g ( q0, b ) = y, g ( q1, a ) = x, g ( q1, b ) = z, g ( q2, a ) = z, g ( q2, b ) = y }
Las funciones f y g deben ser especificadas para cada combinación de cualquier símbolo de entrada con cada estado actual posible. Es muy común denominar a los estado con una q y un subíndice, considerando que q0 sería el estado inicial, aunque ésto es mas bien una costumbre y no una regla.
DIAGRAMA DE TRANSICIÓN DE UNA MÁQUINA DE ESTADO FINITO: Es un grafo dirigido G, en donde los nodos son los estados; el estado inicial se señala con una flecha gruesa sin origen. Si se parte del estado qm y una entrada i proporciona una salida o, y se cambia al estado qn, se traza un arco dirigido de qm a qn y se marca con una ponderación o peso como i / o.
Para este ejemplo se tiene el siguiente diagrama de transición:
Esta descripción gráfica es muy útil, ya que permite observar fácilmente las transiciones que se presentan en la Máquina. Considérese el siguiente análisis, donde se hace un recorrido del digrafo y en donde cada columna representa una transición:
Cadena de entrada: Sin = a b b a a a a b Cadena de salida: Sout = x z z x z x x y Estados recorridos: q0 q1 q1 q1 q2 q0 q1 q2 q1
Una ventaja significativa del diagrama de transición es que el comportamiento de la Máquina de Estado Finito se puede analizar en una forma sumamente "amigable" y sencilla.
Por cada símbolo de entrada, hay un símbolo de salida producido.
TABLA DE TRANSICIÓN DE LA MÁQUINA DE ESTADO FINITO: Se hace la tabla, en la cual se consideran todas las combinaciones S X I colocando en la columna izquierda los estados y en el renglón superior las entradas. En la intersección de los valores particulares de esos dos valores, se coloca el que será el siguiente estado y el símbolo de salida, separados por una coma; en ocasiones, se separan los valores de las funciones f y g en tablas contiguas separadas. Se indica de manera especial el estado inicial con una . A continuación se muestran los dos formatos empleados para la tabla de transición.
I
S a b
q0 q1, x q2 , y
q1 q2, x q1, z
q2 q0, z q1, y
f g
I
S a b a b
q0 q1 q2 x y
q1 q2 q1 x z
q2 q0 q1 z y
Las dos variaciones anteriores representan la tabla de transición; el alumno deberá elegir la que le resulte más adecuada. Esta representación es necesaria para la implementación del software que corresponde a la Máquina, ya que resulta obvio que es más sencillo programar un arreglo, que un gráfico.
Además es imprescindible en los casos en los que se cuenta con muchos estados y muchas entradas, y se corre el riesgo de que un diagrama de transición se convierta en una auténtica "telaraña" por tantos trazos.
Dada una cualquiera de las tres representaciones posibles de M debe ser posible, sin ambigüedades, de obtenerse las otras dos.
EJEMPLO: Diseñar el diagrama de transición y los 6 conjuntos que definen formalmente a la Máquina de Estado Finito de la siguiente tabla de transición:
I
S a b c A A, 0 C, 1 C, 0 B D, 1 A, 0 C, 1 C B, 0 C, 1 A, 0 D D, 0 C, 0 A, 1
Diagrama de transición.
M = ( I, O, S, f , g, 0 )
I = { a, b, c } O = { 0, 1 } S = { A, B, C, D } 0 = { B }
f = { f ( A, a ) = A, f ( A, b ) = C, f ( A, c ) = C, f ( B, a ) = D, f ( B, b ) = A, f ( B, c ) = C, f ( C, a ) = B, f ( C, b ) = C, f ( C, c ) = A, f ( D, a ) = D, f ( D, b ) = C, f ( D, c ) = A }
g = { g( A, a ) = 0, g ( A, b ) = 1, g ( A, c ) = 0, g ( B, a ) = 1, g ( B, b ) = 0, g ( B, c ) = 1, g ( C, a ) = 0, g ( C, b ) = 1, g ( C, c ) = 0, g ( D, a ) = 0, g ( D, b ) = 0, g ( D, c ) = 1 }
P.S. Es muy común denominar a los estados con una q y un subíndice, pero no es una regla, como se acaba de observar. Tampoco es obligado que el primer estado en orden de aparición sea el inicial. Los símbolos de entrada y los de salida no tienen necesariamente una relación entre ellos y pueden ser iguales o diferentes entre sí.
EJEMPLO: Diseñar una Máquina de Estado Finito, considerando como dato de entrada posible cualquier cadena de bits válida. Si el dato de entrada contiene una cantidad par de 1 la salida es 1; 0 en caso contrario.
En este caso, emplearemos la notación más amigable, que es la del diagrama de transición. Consideremos que los bits de la cadena de entrada van llegan uno por uno (en serie) ya que la Máquina de Estado Finito contiene una única entrada y no recibe varios bits a la vez. Es importante definir los estados, como punto de partida; en este caso existen dos posibles: o la cantidad de unos es par o dicha cantidad es impar. La cantidad de ceros en la entrada es totalmente intrascendente, por lo que no hay cambio de estado alguno; éstos se traducen en lazos en el diagrama, sin importar cuál es el estado actual. Sin embargo, la cantidad de unos en la entrada, sí es extremadamente importante, ya que son los que se nos pide que cumplan con ser una cantidad par. Es evidente que en estos casos sí debería de haber cambio de estado actual, de un estado al otro. Llamemos q0 al estado en el cual la cantidad de unos es par, y q1 al estado donde es impar dicha cantidad. Al inicio tenemos cero unos, y siendo cero un número par, definamos a q0 como el estado inicial.
0/ 1 0 / 0
1 / 0
q0 q1
1 / 1
Al iniciar el funcionamiento de la Máquina, la salida debe ser 1, ya que sí se cumple la condición; mientras que no exista ningún 1, sigue estando en esa condición. Cuando aparece el uno, la salida se convierte en 0, y así se quedará hasta que vuelva a aparecer otro 1, quedando la situación igual que al principio (tener 0, 2, 4, 6, 8 ... unos, es equivalente, ya que siempre se cumple con una cantidad par). Finalmente, hay que observar cuál es el bit de salida, cuando llega el último bit de entrada.
EJEMPLO: Diseñar una Máquina de Estado Finito que represente un sumador binario en serie.
Primeramente habrá que considerar que la mencionada será una suma de cadenas de bits, en la que éstos se sumarán de dos en dos a la vez, uno del primer sumando y el otro del segundo. La longitud de las dos cadenas a sumar es la misma para este ejemplo y puede ser cualquier cantidad de bits. Un ser humano realiza la suma en serie cuando la realiza sin calculadora. Veamos un ejemplo de una suma binaria en serie, como muestra:
1 1 1
1 0 0 1 0 0 1 0 + Ejemplo de una
1 0 1 0 0 1 1 1 suma binaria en serie
1 0 0 1 1 1 0 0 1
Nótese que al sumar dos bits, el bit resultado varía; por ejemplo al hacerlo con 0 + 0, tenemos que da 0 (cuando no hay acarreo) ó 1 (cuando sí hay un acarreo). El existir o no acarreo representa un estado del sistema, que influye en el bit de salida.
De acuerdo al conocimiento, tanto de la operación de la suma como de las Máquinas de Estado Finito, se determinan los conjuntos:
I = { 00, 01, 10, 11 } O = { 0, 1 } S = { SA, CA } 0 = { SA }
Recuérdese que un símbolo de entrada se puede formar por más de un caracter, por lo que las entradas pueden expresarse con un par de caracteres, que representan los bits que se están sumando (por ejemplo 00 significa 0 + 0). Este hecho permite que se puedan tener Máquinas que representen sistemas en los que hay varias entradas, pero canalizadas todas ellas por una sola. Si no fuese así, entonces tendríamos que definir modelos de Máquinas con varias entradas, lo cual sería un tanto complicado.
En este caso SA significa "Sin Acarreo" y CA es por "Con Acarreo". Cuando empezamos a sumar lo hacemos desde un estado inicial sin acarreo. Cuando se suman dos bits el resultado es un solo bit y si el resultado excede tal, de todas formas se escribe un bit y se pasa a un estado con acarreo.
Finalmente, resulta el siguiente diagrama de transición para el sumador:
Es muy recomendable que el alumno, una vez que resuelva un problema, haga una comprobación del funcionamiento del modelo formal, para ver si funciona en casos extremos, He aquí la verificación de la suma ya anteriormente evaluada, ahora con el Diagrama de Transición que se acaba de diseñar:
Sin = 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 1 Sout = 1 0 0 1 1 1 0 0 SA SA CA CA SA SA SA SA CA
La versión previa de sumador tiene el inconveniente de que el bit más significativo se pierde si el resultado excede en un bit a la longitud de los sumandos. Lo anterior no es un problema serio, ya que en algunos casos así es el modelo real que estamos emulando; por ejemplo, el chip de un circuito integrado sumador (TTL o CMOS) tiene como terminales o pines para cada entrada, la misma cantidad que la de los pines donde se muestra la suma de las dos cadenas de bits, mostrando el posible bit adicional más significativo en el pin de acarreo (que no es una terminal de salida).
Como comprobación del aprendizaje se pide al alumno proponer una variante al sumador anterior tal que el resultado lo entregue íntegro. Además se puede diseñar una Máquina de Estado Finito en la que se puedan sumar cadenas de longitudes diferentes. Considerar como posibles entradas 0 + símbolo vacío, 1 + símbolo vacío, símbolo vacío + 0, símbolo vacío+ 1, etc.
Sin embargo, no existe una Máquina de Estado Finito que pueda realizar la multiplicación binaria en serie. ¿Por qué?
Al inicio del módulo se afirmó que este modelo tenía una memoria interna primitiva. Esa afirmación se justifica en el hecho de que al operar, una Máquina de Estado Finito "sabe" con toda certeza cuál es su estado actual, pero "no recuerda" cómo llegó al mismo. Como se verá en un ejemplo a resolver, esa situación impide que pueda reconocer cadenas con la misma cantidad de diferentes símbolos, tales como los paréntesis cuando se anidan correctamente. Esa limitación es muy importante en aplicaciones computacionales.
EJEMPLO: CONTADOR SÍNCRONO DE 3 BITS Diseñar un contador síncrono de 3 bits con flip flops tipo D. En este caso es adecuado utilizar una Máquina de Estado Finito (porque la salida no es un simple bit, sino tres). De hecho, se deben evaluar los valores que debe haber en las entradas de cada uno de los flip flop tipo D que se van a emplear para obtener el conteo requerido.
? ? ?
D1 Q1 D2 Q2 D3 Q3
FF1 FF2 FF3
MSB LSB
Si se evalúa la expresión lógica de las entradas a los tres flip-flops, se podrán obtener, combinando las tres salidas, los valores binarios deseados. Para mayor claridad, apoyarse de un texto sobre la materia.
El Diagrama y la Tabla de Transición obtenidos para las especificaciones de diseño de dicho contador de tres bits serían los siguientes:
f g
S I 0 1 0 1
Q1 Q2 Q3 Q1 Q2 Q3 Q1 Q2 Q3 Q1 Q2 Q3 Q1 Q2 Q3
0 0 0 0 0 1 0 0 0
0 0 1 0 1 0 0 0 1
0 1 0 0 1 1 0 1 0
0 1 1 1 0 0 0 1 1
1 0 0 1 0 1 1 0 0
1 0 1 1 1 0 1 0 1
1 1 0 1 1 1 1 1 0
1 1 1 0 0 0 1 1 1
La anterior es la Tabla de Transición de una Máquina de Estado Finito, conocida en electrónica como tabla de verdad. La salida y el siguiente estado no se consideran cuando la entrada (en el reloj) es 0, porque éstos no ocasionan acción alguna en el circuito.
Los diagramas de Karnaugh para determinar las entradas de los 3 flip flops, deducidas de la tabla anterior, son:
Q1 Q2
Q3 0 0 0 1 1 1 1 0
0 1 1 FF1
1 1 1
D1 = Q1 Q2 Q3 + Q1 Q3 + Q1 Q2
Q1 Q2
Q3 0 0 0 1 1 1 1 0
0 1 1 FF2
1 1 1
D2 = Q2 Q3 + Q2 Q3 = Q2 + Q3
Q1 Q2
Q3 0 0 0 1 1 1 1 0
0 1 1 1 1 FF3
1
D3 = Q3
El circuito contador de tres bits se obtiene a partir de las ecuaciones para las entradas en los tres flip flops: D1, D2 y D3, recientemente obtenidas. Cada uno de los tres flip-flops debe recibir la entrada según la expresión lógica correspondiente. Queda como trabajo para el estudiante diseñar el diagrama electrónico resultante.
Nótese que las Tablas de Transición se emplean en estas aplicaciones, aunque sin haberlas justificado, en cursos de electrónica digital secuencial. Para obtener mayor información de estas aplicaciones consúltense libros sobre la materia.
Para comprender la utilización de los modelos matemáticos de este curso, es recomendable tener conocimientos sobre Sistemas Digitales Secuenciales.
CONCEPTOS ADICIONALES:
Existen muchos diferentes tipos de Máquinas de Estado Finito para modelar máquinas de cómputo, que son llamadas Máquinas secuenciales. En el tipo tradicional las salidas corresponden a transiciones entre estados. Las representaciones de este tipo son conocidas como Máquinas de Mealy, ya que fueron primeramente estudiadas por G. H. Mealy en 1955. Existe otro tipo importante de Máquina de Estado Finito con salida, donde esta última es determinada sólo por el estado. Se le conoce como Máquina de Moore, ya que E. F. Moore introdujo este tipo de Máquina en 1956. Se observa una estrecha relación de las Máquinas de Mealy con las de Estado Finito y de la de Moore con los Autómatas de Estado Finito.
Una Máquina de Moore puede convertirse en una de Mealy equivalente añadiendo más estados y haciendo las modificaciones necesarias.
Queda para el estudiante investigar más sobre estas dos variantes de Máquinas de Estado Finito, muy usuales en Circuitos Digitales Secuenciales.
Un proyecto final de este curso consistirá en diseñar y simular en la computadora, una aplicación de este modelo en un caso práctico.
Hay una relación muy estrecha entre Máquinas y Autómatas de Estado Finito. De hecho, éstos últimos son un subconjunto de las primeras. La forma como se relacionan se estudiará en el siguiente capítulo.
Queda pendiente el empleo de las Máquinas de Estado Finito para representar sistemas electrónicos, computacionales o, en general, del mundo real. En el siguiente módulo se analizarán casos de aplicación, como la máquina de refrescos, diseñada cómo Máquina y como Autómata de Estado Finito.