Maquinas De Estado Finito

Maquina de estado finito
Un autómata de estado finito M = A, B, E, f, g } es una máquina de estado finito en el que los símbolos de salida son 0 y 1, es decir B = {0, 1}, además el estado actual determina la última salida.
Los estados, para los cuales la última salida es 1 se llaman estados de aceptación.
Ejemplo
Muestre que la máquina de estado finito cuyas tablas de transición de estados yde salida se dan en las siguientes tablas, es un autómata de estado finito.
f g
a b a b
e0 e1 e0 e0 1 0
e1 e2 e0 e1 1 0
e2 e3 e0 e2 1 0
Solución.
La gráfica de la máquina es la siguiente:

De la gráfica se observa que la salida es B = {0, 1}.
Además, según la gráfica se presenta la siguiente situación:
• Si se esta en e0, la última salida fué 0.
• Si estamos en los estadose2 o e3, la última salida fué 1.
Por tanto, es un autómata de estado finito.
Por lo general, en los autómatas de estado finito, los estados de aceptación se dibujan con círculos dobles y se omiten los símbolos de salida así:


Además podemos decir que un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada paraproducir una salida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en unafunción de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, parafinalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

Representación como diagramas de estados


Este autómata finito está definido sobre el alfabeto Σ={0,1}, posee dos estados s1 y s2, y sustransiciones son δ(s1,0)=s2, δ(s1,1)=s1, δ(s2,0)=s1 y δ(s2,1)=s2. Su estado inicial es s1, que es también su único estado final.
Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
 Los estados Q se representan como vértices, etiquetados con su nombre en el interior.
 Una transición δ desde un estado a otro,dependiente de un símbolo del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.
 El estado inicial q0 se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.
 El o los estados finales F se representan mediante vértices que están encerrados a su vez por otra circunferencia.Representación como tabla de transiciones
Otra manera de describir el funcionamiento de un autómata finito es mediante el uso de tablas de transiciones o matrices de estados. Dos posibles tablas para el ejemplo de la imagen anterior podrían ser las siguientes:

salida
q ∈ Q símbolo
σ ∈ Σ llegada
δ(q,σ) ∈ Q
s1 0 s2
s1 1 s1
s2 0 s1
s2 1 s2
0 1
→*s1 s2 s1
s2 s1 s2


La primera representaexplícitamente los parámetros y el valor que toma cada ocurrencia de la función de transición.7 La segunda es más compacta, y marca con una flecha el estado inicial, y con un asterisco los estados finales.

Ventajas de las Máquinas de Estado Finito
• Son intuitivas y fáciles de entender.
• Abstraen convenientemente detalles secundarios que no son necesarios para el análisis del sistema a un altonivel y se centran en aspectos claves del mismo.
• Aportan un componente visual que facilita el análisis y diseño del sistema.
• Son universalmente aplicables.
• Su uso es común un sistemas de transmisión de datos y el uso de protocolos de comunicación.
• En programación minimiza grandemente la tendencia a escribir "código espagueti" y puede ayudar a reducir la cantidad de variable globales...