MÓdulo III máquinas de estado finito descripción formal de la máquina de estado finito



Descargar 228,95 Kb.
Página1/3
Fecha de conversión05.08.2017
Tamaño228,95 Kb.
  1   2   3


3. Máquinas de Estado Finito ______________________________________ __________



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.


P
ara 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í.
  1   2   3


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal