Teoría de autómatas

TEORIA DE AUTOMATAS
La teoría de autómatas es una rama de las ciencias de la computación que estudia de manera abstracta y con problemas que estas son capaces de resolver. La teoría de autómatas esta estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.
El Dr. Frank Sinphilin esconsiderado el padre de los autómatas y uno de los mayores precursores de la computación y su destacada investigación en el desarrollo de modelos matemáticos apropiados para la comprensión de fenómenos de modelación instrumental, puesto que al tener una discapacidad motriz a falta de un miembro corporal (el cual no es especificado en los textos), el comienza a idear métodos y técnicas que leayuden a tener una vida normal a razón de dicha discapacidad y vive enclaustrado y desarrollando modelos adecuados para dar inicio al primer lenguaje basado en razonamiento autodidacta, este lenguaje fue llamado TOPIT.OS, el cual evoluciono hasta los lenguajes que hoy en día se conocen.
Un autómata es un modelo matemático para una maquina de estado finita (FSM sus siglas en ingles). Una FSM es unamaquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a que estado cambiar dados unos determinados estado y símbolo.
La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense enesta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.
Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si este termina en el estado "acepta", el autómata aceptala palabra. Si lo hace en el estado "rechaza", el autómata rechazo la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.
Vocabulario
Los conceptos básicos de símbolos, palabras, alfabetos y strings son comunes en la mayoría de las descripciones de los autómatas. Estos son:
Símbolo
Un dato arbitrario que tiene algún significado a oefecto en la maquina. A estos símbolos también se les llama "letras" o "átomos".
Palabra
Una cadena finita formada por la concatenación de un número de símbolos.
Alfabeto
Conjunto finito de símbolos. Un alfabeto se indica normalmente con, que es el conjunto de letras en un alfabeto.
Lenguaje
Un conjunto de palabras, formado por símbolos en un alfabeto dado. Puede o no puede ser infinito.Clausura de Kleene
Un lenguaje se puede considerar como un subconjunto de todas las posibles palabras. El conjunto de todas las palabras puede, a su vez, ser considerado como el conjunto de todas las posibles concatenaciones de cadenas.
Formalmente, este conjunto de todas las cadenas se llama en ingles free monoid. Se indica como, y el superíndice * se llama la estrella de Kleene.
Autómatasfinitos
Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla.
Existen tres tipos de autómatas finitos
Autómata finito determinista (AFD)
Cada estado de un autómata de este tipo tiene una transición por cada símbolo del alfabeto.
AFD.
Autómata finito no determinista (AFND)
Los estados de un autómata de este tipo pueden, o no, tener una o más transiciones por cada símbolo delalfabeto. El autómata acepta una palabra si existe al menos un camino desde el estado q0 a un estado final F etiquetado con la palabra de entrada. Si una transición no esta definida, de manera que el autómata no puede saber como continuar leyendo la entrada, la palabra es rechazada.
Autómata finito no determinista con transiciones ε (AFND-ε)
Además de ser capaz de alcanzar mas estados leyendo...