12.2 M�quinas de Estado Finito

12.2.1 Definici�n. Una m�quina de estado finito M se caracteriza por:

- Un conjunto finito A de s�mbolos de entrada.
- Un conjunto finito E de estados internos.
- Un conjunto finito B de s�mbolos de salida.
- Una funci�n de pr�ximo estado f de E x A ® E .
- Una funci�n de salida g de E x A ® B .

Esta m�quina se denota por M = { A, B, E, f, g }; por lo general se da un estado inicial .

Ejemplo 1.

En una estaci�n del Metro una m�quina distribuye tiquetes sencillos a $600 pesos el tiquete. La m�quina acepta monedas de $100, $200, $500, $1000. Mediante una tabla, describa los diferentes estados de la m�quina y la salida.

Soluci�n.

Se supondr� que la m�quina se encuentra en el estado e₀ perteneciente a E en el tiempo t₀. Al introducir una moneda en el tiempo t_i la salida ser� g(x,e_s) donde e_s es el estado de la m�quina en el tiempo t_i. A esta salida le sigue una transici�n de la m�quina en el tiempo t_i+1dado por f(x,e_s).

Para el ejemplo, los estados del conjunto E ser�n:

e₀ = Estado inicial de la m�quina sin introducir monedas.
e₁ = La m�quina recuerda la inserci�n de $100.
e₂ = La m�quina recuerda la inserci�n de $200.
e₃ = La m�quina recuerda la inserci�n de $300.
e₄ = La m�quina recuerda la inserci�n de $400.
e₅ = La m�quina recuerda la inserci�n de $500.
e₆ = La m�quina recuerda la inserci�n de $600 o m�s pesos.

La funci�n f: E x A ® E donde A = { n, 100, 200, 500, 1000, b } es la entrada donde n detalla el hecho de no introducir monedas y b hundir bot�n para obtener el tiquete, se detalla en la siguiente tabla:

En esta tabla por ejemplo, f(e₀,500)=e₅; lo que quiere decir que en el tiempo t siguiente la m�quina recordar� que se le han introducido $500.

f(e₃,200)=e₅ , lo que significa que la m�quina pasa del estado e₃; al estado e₅ ; lo que quiere decir que pasa de "recordar" que se le habr�an introducido $300 a "recordar" que se le han introducido $500.

f(e₅,200)=e₆ , lo que significa que la m�quina pasa de "recordar" que se le habr�an introducido $500 a "recordar" que se le han introducido m�s de $600, en este caso, la funci�n de salida se dise�ar� para que devuelva $100 al comprador.

Al pulsar el bot�n, la m�quina pasar� al estado e₀; si el estado actual es e₀ � e₆.

La funci�n g:E x A ® B es la funci�n de salida, que se detalla en el siguiente cuadro:

En esta tabla, por ejemplo, g(e₃,500) = 200, lo que significa que la máquina pasa de "recordar" que se le habían introducido $300 a "recordar" $800 y por tanto devuelve $200. Como f(e₃,500)=e₆, la máquina pasa al estado e₆ y por último, como g(e₆,b)=T recibe el tiquete.

Como f(e₆,b)=e₀, la máquina retorna al estado inicial.

El conjunto de salida B será:

B = { n, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, T}

acá: n significa que no hay salida.

T significa que se entrega el tiquete.

Ejemplo 2.

Sean X = X₅X₄X₃X₂X₁ = 00111, Y = Y₅Y₄Y₃Y₂Y₁ = 01101 número binarios, donde X₁,Y₁ son los bits menos significativos. Los ceros iniciales de X e Y son para que las cadenas X e Y sean de igual longitud y poder garantizar suficientes lugares para completar la suma.

Un sumador binario en serie es una máquina de estado finito que se puede usar para obtener X + Y.

En la suma X+ Y, se tiene:

X =    0 0 1 1 1
Y = + 0 1 1 0 1
Z =    1 0 1 0 0

Se observa que para la primera suma mirando de derecha a izquierda X₁ = Y₁ = 1 y Z₁ = 0, mientras que para la tercera suma mirando de derecha a izquierda, X₃ = Y₃ = 1 y Z₃ = 1 debido al acarreo de la suma de X₂ e Y₂ y de X₁ y Y₁.

En consecuencia, cada salida depende de la suma de las dos entradas y la capacidad para recordar, si se acarrea 0 o 1 que es crucial cuando es 1.

El sumador binario en serie se elabora mediante una máquina de estados finitos de la siguiente forma:

E = {e₀,e₁} donde e₀ = 0 y e₁ = 1

A = { 00, 01, 10, 11 }

B = { 0, 1 }

Las tablas se detallan a continuación:

Lo que realiza f : E x A ® E es recordar si hay o no hay acarreo.

En las tablas anteriores se observa que:

f(1,01) = 1 y g(1,01) = 0 porque e₁ = 1; significa que se lleva 1 de la suma de los bits anteriores, la entrada 01 significa que se suman 0 y 1 y se acarrea 1. De ahí que la suma sea 10 y g(1,01) = 0 por el 0 en 10.

Ejemplo 3.

Diseñe una máquina de estado finito que produce salida 1 si la entrada es un número par de unos, produce la salida 0 en caso contrario.

Los dos estados de la máquina serán P e I donde P es par e I es impar. El estado inicial es 0, que es un número par.

La tabla de transición de estados es la siguiente:

La tabla de salida será:

Así, por ejemplo, si la entrada es 11101 entonces la salida vendrá dada por:

g(P,11101) = g(g(P,1),1101)

  = g(I,1101)

  = g(g(I,1),101)

  = g(P,101) = g(g(P,1),01)

  = g(I,01) = g(g(I,0),1)

  = g(I,1) = 1

Ejemplo 4.

Diseñe una máquina de estado finito que produce salida 1 siempre que vea 101; produce la salida 0 en caso contrario.

Solución.

Acá A = {0, 1}, B = {0,1}. El estado inicial e₀ se mantendrá si la entrada es 0 y cambiará a e₁ si la entrada es 1; es decir f(e₀,0)=e₀; f(e₀,1)=e₁.

El estado e₁ se mantendrá si la entrada es 1 y cambiará a e₂ si la entrada es 0; es decir f(e₁,0)=e₂; f(e₁,1)=e₁.

El estado e₂ cambiará a e₀ si la entrada es 0 y cambiará a e₁ si la entrada es 1 y acá la salida será 1. Las demás salidas serán 0.

La tabla de transición de estados es:

La tabla de salida es:

Así por ejemplo, si la entrada es 101 la máquina hará lo siguiente:

• Al entrar 1 es estado cambia de e₀ a e₁ y la salida será 0.
• Al entrar 0 el estado cambia de e₁ a e₂ y la salida es 0.
• Al entrar 1 es estado cambia de e₂ a e₁ y la salida será 1.

Esta situación la podemos representar también, mediante un diagrama de transición donde los vértices o círculos serán los estados. El estado inicial se indica mediante una flecha. Si una entrada produce un cambio de estado del vértice e_i al vértice e_k, se traza una arista dirigida de e_i a e_k y se etiqueta como x/s donde x es la entrada y s es la salida. Si no hay cambio de estado, se traza un lazo dirigido sobre el vértice que representa ese estado.

En el ejemplo anterior, el diagrama de transición es: