M quinas de Estado Finitos

Introducción


En esta era de computadores y telecomunicaciones, nos
enfrentamos día a día a situaciones de entrada y salida. Por ejemplo, al
comprar un refresco en una máquina expendedora, damos como entrada
ciertas monedas y después oprimimos un botón para obtener la salida
esperada, es decir, el refresco. La primera moneda que damos comoentrada pone la máquina en movimiento. Aunque generalmente no nos
preocupamos acerca de lo que ocurre dentro de la máquina (a menos que
se descomponga y tengamos una pérdida), convendría notar que, de
alguna forma, la máquina lleva un registro de las monedas depositadas,
hasta que se introduce el importe correcto. Sólo entonces, y no antes, la
máquina deja salir el refresco esperado. En consecuencia, para que elvendedor tenga la ganancia esperada por cada refresco, la máquina debe
recordar internamente, conforme se va insertando cada moneda, la suma
de dinero depositado.


Las principales características de estas máquinas son:


1. La máquina solo puede estar en uno de una cantidad finita
de estados en un instante dado. Estos estados son los estados
internos de la máquina y, en un instante dado, la memoriatotal disponible de la máquina es el conocimiento del estado
interno en el que se encuentra en ese instante.
2. La máquina aceptará como entrada sólo un número finito de
símbolos, que se conocen en conjunto como el alfabeto de
entrada ∆. En el ejemplo, el alfabeto de entrada es {moneda
de 5 centavos, moneda de 10 centavos, blanco, negro}, y cada
elemento se reconoce por su estado interno.
3. Mediante cada combinación de entradas y estados internos sedetermina una salida y un estado siguiente. El conjunto
finito de todas las salidas posibles constituye el alfabeto de
salida de la máquina.
4. Suponemos que los procesos secuenciales de la máquina
están sincronizados por pulsos de reloj separados y distintos
y que la máquina opera de manera determinista, ya que la
salida queda completamente determinada por la entradatotal proporcionada y el estado inicial de la máquina.


Estas observaciones conducen a definir máquinas de estado finito,
identificar máquinas de estado finito equivalentes, y a resolver diferentes
ejercicios propuestos anteriormente en el aula, dándole oportunidad a la
parte práctica de la teoría vista.




“Dime y lo olvido, enséñame y lo recuerdo, involúcrame y lo aprendo”.
Benjamin Franfklin.
Máquinas de Estado FinitoUna máquina de estado finito (MEF) es una estructura 5-upla
M =(S, v, ω, ∆, σ) de S es el conjunto de estados internos de M; no vacíos y
finitos, ∆ es el alfabeto de entrada de M, σ es el alfabeto de salida de M;
dos aplicaciones v: S x ∆ →S es la función siguiente estado; y ω: S x → σ
es la función de salida.


Según la notación de esta definición, si la máquina está en estado Sen el instante ti e introducimos x en ese momento, entonces la salida en
el instante ti es ω(s,x). Esta salida es seguida por una transición de la
máquina, en el instante ti+1 al siguiente estado interno, dado por v(s,x).


Suponemos que cuándo una máquina de estados finitos recibe su
primera entrada, estamos en el instante to = 0 y la máquina está en unestado de inicio ya determinado, denotado con so. Nuestro desarrollo se
concentrará principalmente en la salida y las transiciones de estado que
ocurren de manera secuencial, con poca o ninguna referencia a la
sucesión de pulsos de reloj en los instantes to, t1, t2, ..


Puesto que los conjuntos S, ∆ y σ son finitos, es posible representar
v y ω, para una máquina de estados finitos dada, por medio de una tablaque enumera v(s,x) y ω(s,x) para todo s que pertenece a S y todo x que
pertenece ∆, y que se conoce como la tabla de estados o tablas de
transición de la máquina dada. Una segunda representación de la
máquina se hace por medio de un diagrama de estados.
Ejemplos


Consideremos la máquina de estados finitos M = (S, ∆, σ, v, ω),
donde S = {so, s1, s2}, ∆ = {0,1} = σ y v,ω aparecen en la tabla de estados a...