AUTÓMATAS FINITOS

AUTÓMATAS FINITOS

• AUTÓMATAS FINITOS:

El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX. Ya en 1907, el matemático ruso Andréi Márkov formalizó un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior.Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo o palabra presente en la función de transición.

Posteriormente, en 1943, surge una primera aproximación formal de los autómatas finitos con el modelo neuronal de McCulloch-Pitts. Durante la década de 1950 prolifera su estudio, frecuentemente llamándose les máquinas de secuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación como lenguajes regulares y su equivalencia con las expresiones regulares.Al final de esta década, en 1959, surge el concepto de autómata finito no determinista en manos de los informáticos teóricos Michael O. Rabin y Dana Scott.

•  SISTEMA DE ESTADOS FINITOS:

El autómata finito es un modelo de un sistema, con entradas y salidas discretas. El sistema pude estar en cualquiera de un número finito de configuraciones o "estados". El estado del sistema resume la información concerniente a entradas anteriores y que es necesaria para determinar el comportamiento del sistema para entradas posteriores.

El mecanismo de control de una máquina de refrescos es un buen ejemplo de un sistema de estados finitos. 
Si no introducimos ninguna moneda y presionamos el botón de cualquier refresco, la máquina nos informa del precio del refresco seleccionado.
Si introducimos un importe inferior al precios del refresco la máquina nos informa del valor del refresco y queda a la espera de que se introduzca más monedas.
Si introducimos el importe exacto, la máquina nos expenderá el refresco seleccionado.
Si introducimos más dinero del necesario la máquina nos devolverá el cambio por la diferencia entre el importe introducido y el valor del refresco seleccionado.  

• DEFINICIÓN DE UN AUTÓMATA FINITO:

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
Éstos se definen mediante una quíntupla (E, Q, f, q0, F ) donde:

E: alfabeto de entrada.

Q: conjunto de estados; es conjunto finito no vacío.

f: función de transición. f(p,a)=q

q0 : (perteneciente a Q) estado inicial.

F : (perteneciente a Q) conjunto de estados finales o de aceptación.

• LENGUAJES RECONOCIDOS POR UN AUTÓMATA FINITO:

AF como reconocedor de un Lenguaje:

• Cuando un AF transita desde q0 a un estado final en varios movimientos, se ha producido el RECONOCIMIENTO o ACEPTACIÓN de la cadena de entrada.
• Cuando un AF no es capaz de alcanzar un estado final, se dice que el AF NO RECONOCE la cadena de entrada y que ésta NO PERTENECE al lenguaje reconocido por el AF.

Ejemplo:

A partir del autómata, comprobar si reconoce la palabra “aabbaba”.

Empezaríamos en el estado P, al recibir una "a", pasaríamos a Q, al recibir una "a" de nuevo,Seguiríamos en Q, después al recibir una "b", pasaríamos a R, y recibiendo otra "b", seguiríamos en R. A continuación recibiríamos una "a", que nos llevaría a R y así hasta el final. Por lo tanto al quedar después de la palabra leída en el estado R, y dado que este no es un estado final como lo es Q, la palabra no se reconocería. En cambio la palabra “aa” si que se reconocería puesto que terminaríamos en el estado final Q. Se trata por tanto de un autómata que reconoce lenguajes formados exclusivamente por una o varias “a”.

• REPRESENTACIÓN DE LOS AUTÓMATAS FINITOS:

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

Tablas de transición:

• Filas encabezadas por los estados( Q )

• Columnas encabezadas por los símbolos de entrada ( E)

Diagramas de transición:

• Nodos etiquetados por los estados(Q)

• Arcos entre nodos etiquetados con ( E)

• Q0 se señala con ->

• El estado final se señala con * o con doble circulo

• DIAGRAMA DE MOORE:

Una máquina de Moore puede ser definida como una 6-tupla { S, S₀, Σ, Λ, T, G } consistente de

• un conjunto finito de estados ( S )
• un estado inicio (también llamado estado inicial) S₀ el cual es un elemento de (S)
• un conjunto finito llamado alfabeto entrada ( Σ )
• un conjunto finito llamado el alfabeto salida ( Λ )
• una función de transición (T : S × Σ → S) mapeando un estado y una entrada al siguiente estado
• una función salida (G : S → Λ) mapeando cada estado al alfabeto salida.

El número de estados en una máquina de Moore será mayor o igual al número de estados en la Máquina de Mealy correspondiente.

AQUI LES DEJO UN VIDEO DONDE EXPLICA EL TEMA............

RECURSOS:

LIBROS ELECTRÓNICOS

Yannis Haralambous “Fonts & Encodings”, O'Reilly Media, Inc., (2007)

Disponible en safari.

LIBROS

• Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón." Teoría de autómatas y lenguajes formales". McGraw-Hill (2007). Capítulos 3 y 7.