Automatas

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está 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 es considerado elpadre 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 le ayuden a tener unavida 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 evolucionó hasta los lenguajes que hoy en día se conocen.
Un autómata es un modelo matemático para una máquina de estado finita (FSM sus siglas en inglés). Una FSM es una máquina que, dadauna 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 un determinado estado y símbolo.
La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en esta como una cintacon 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 acepta la palabra. Si lohace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

Autómatas finitos
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, unconjunto 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 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, para finalmente detenerse en un estado final o de aceptación, que representa lasalida.
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.
Historia

El modelo neuronal de McCulloch-Pitts también utiliza diagramas con estados y transiciones, además de los conceptos de entrada y salida.
El origen de los autómatas finitos probablemente se remonta a su uso implícitoen máquinas electromecánicas, desde principios del siglo XX.[1] 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.[2] Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activaciónde 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ándoseles máquinas de secuencia; se establecen muchas de sus propiedades básicas,...