lenguajes formales

LENGUAJES FORMALES Y AUTOMATAS
Conceptos básicos
Mostrar los conceptos básicos acerca de la teoría de lenguajes formales, autómatas finitos y gramáticas. Estudiar en profundidad la clase de los lenguajes regulares. Mostrar distintos modelos de autómatas finitos así como su equivalencia. Introducir las expresiones regulares como método de descripción de lenguajes regulares. Estudiar algunaspropiedades de la clase de los lenguajes regulares. Mostrar los conceptos básicos acerca de la clase de lenguajes incontextuales. Introducir el modelo de cálculo de la máquina de Turing y estudiar su relación con las clases de lenguajes recursivos y recursivamente enumerables. Introducir los conceptos básicos de la Teoría de la Complejidad así como sobre las funciones recursivas y la indecidibilidadgramatica tipo 3 y automata finito

gramatica tipo 2 y automata push down
gramatica tipo 0 y maquina de turing
gramatica tipo 1 y automata lineal con frontera o acotado
Autómata finito
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 representala 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 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 usoimplícito en 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ón deun 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,incluyendo su interpretación como lenguajes regulares y su equivalencia con las expresiones regulares.1 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.3
En la década de 1960 se establece su conexión con las series de potencias y los sistemas de sobreescritura.4 Finalmente, con el desarrollo delsistema operativo Unix en la década de 1970, los autómatas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines prácticos, específicamente en el diseño de analizadores léxicos (comando lex) y la búsqueda y reemplazo de texto (comandos ed y grep).5 A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.1
Definición formalFormalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:6
• 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.
El esquema general es el de una cinta lectora que avanza sólo hacia delante y de a una celda, según la función de transición.
Funcionamiento
En...