Maquina de estado finito

¿Qué es una maquina de estado finito?

     Una máquina de estado finito es una máquina abstracta que reconoce cadenas de caracteres dando una respuesta de “SÍ” o “NO” basada en las transiciones entre “estados” de la máquina, las transiciones se escogen en base al siguiente carácter de la cadena.

También se puede 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 para producir una salida.

¿Cómo funciona?

la maquina de estado finito funciona abstrayendo computacionalmente el comportamiento descrito de un sistema reactivo mediante un número determinado de Estados y un número determinado de Transiciones entre dicho Estados.

Diagrama de Estado Finito:

Un Diagrama de Estado Finito es un gráfico que representa los diferentes estados de una MEF y todas las transiciones posibles entre los estados.

Como ejemplo, consideremos un muy simplificado sistema de control de un ascensor:

El cual esta compuesto por:

Definición formal:

Formalmente, un autómata finito es una 5-tupla (Q, Σ, q₀, δ, F) donde:

•  es un conjunto finito de estados.

•  es un alfabeto finito.

•  es el estado inicial.

•  es una función de transición.

•  es un conjunto de estados finales o de aceptación.

diagramas de estados:

os 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 q₀ 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. de esta forma:

existen maquinas de estado finito determinista y no-determinista:

Determinista:

 Este tipo de autómatas admite su definición de dos maneras bien diferentes, como autómatas traductores o reconocedores. La definición como autómatas traductores continua a la definición de las máquinas secuenciales, y se los podría definir como una subclase de estas, ya que los autómatas finitos tendrían como limitante no poder iniciar desde cualquier estado como lo hacen en las máquinas secuenciales.

La forma que adoptaremos para la definición de los autómatas finitos deterministas es como autómatas reconocedores, ya que se ajusta  con los contenidos de la informática teórica  y utilización que se les da dentro del diseño de los analizadores léxicos. Estos autómatas solo se limitarán a aceptar o no una determinada cadena recibida en la entrada, por lo tanto podemos decir que la salida de los mismos solo tendrá dos valores posibles aceptar o no aceptar a la palabra de entrada.

No-Determinista:

Un autómata o maquina de estado finito no determinista  es un autómata finito que, a diferencia de los autómatas finitos deterministas , posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

En un AFND puede darse cualquiera de estos dos casos:

• Que existan transiciones del tipo δ(q,a)=q₁ y δ(q,a)=q₂, siendo q₁ ≠ q₂;
• Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.