TEORÍA DE AUTÓMATAS Y LENGUAJES

GRAMATICAS DEFINICION DE GRAMATICAS: Una gramática (" G ") desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L . Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes. Una gramática es una estructura algebraica formada por cuatro elementos fundamentales: G = { NT , T , S , P } donde NT es el conjunto de elementos No Terminales T es el conjunto de elementos Terminales S es el Símbolo inicial de la gramática P es el conjunto de Reglas de Producción TIPOS DE GRAMATICAS: REGULARES: También llamada "De contexto regular" “α puede ser reemplazado por β si α pertenece a los símbolos No Terminales y β es uno de estos 3: Un símbolo Terminal no nulo seguido de un No Terminal . Un símbolo No Terminal seguido de un símbolo Terminal no nulo. Un símbolo Terminal pudiendo ser la cadena vacía.” M...

MAQUINAS DE TURING CONTENIDO: DEFINICIÓN FORMAL DE LAS M.T. CONSTRUCCIÓN DE LAS M.T. LENGUAJES DE ACEPTACIÓN PARA LAS M.T. M.T COMO E NUMERADORES. M.T RESTRINGIDAS. MAQUINAS DE TURING Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador. Originalmente fue definida por el matemático inglés Alan Turing como una «máquina automática» en 1936, en la revista Proceedings of the London Mathematical Society,​ La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico. ...

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...