Automata Finito

AUTÓMATA FINITO
Autómata del griego automatos (αὐτόματος) que significa espontáneo o con movimiento propio.
Autómata: Máquina que imita la figura y los movimientos de un ser animado.
Autómata programable: Equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales. No tiene sus propios movimientos, sinoque estos parecen ser de robot.

Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir 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 una función de transición, que recibe a partir de unestado 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, para finalmente 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 laJerarquí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 sus transiciones 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. El lenguaje regular que reconoce puede expresarse mediante la expresión regular (00 | 11 | (01 | 10)(01 | 10)) * .Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
* Los estados 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 queestá etiquetada con dicho símbolo.
* El estado inicial se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.
* El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.

AUTÓMATA FINITO DETERMINISTA

AFD que reconoce el lenguaje regular conformado exclusivamente por las cadenas con un número par deceros y par de unos.
Autómata finito determinista
Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).
En un AFD no pueden darse ninguno de estos dos casos:
* Queexistan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
* Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado final, sin transiciones hacia otros estados.
Un ejemplo interesante de autómatas finitos deterministas son los tries.
AUTÓMATA FINITO NO DETERMINISTA

AFND con transiciones δ(q0,b)=q0 y δ(q0,b)=q1, que acepta el lenguaje regular sobre el alfabeto {a,b}conformado por todas las palabras que terminan en b; es decir, que equivale a la expresión regular (a|b)*b+.

Autómata finito no determinista
Un autómata finito no determinista (abreviado AFND) es aquel 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.
Haciendo laanalogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
* Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
* 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...