TEORÍA DE AUTÓMATAS Y LENGUAJES

COMPUTABILIDAD DE PROBLEMAS La  Teoría de la computabilidad  es la parte de la  computación  que estudia los  problemas de decisión  que pueden ser resueltos con un  algoritmo  o equivalentemente con la llamada  máquina de Turing . La teoría de la computabilidad se interesa por cuatro preguntas: ¿Qué problemas puede resolver una máquina de Turing? ¿Qué otros formalismos equivalen a las máquinas de Turing? ¿Qué problemas requieren máquinas más poderosas? ¿Qué problemas requieren máquinas menos poderosas? La  teoría de la complejidad computacional  clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina. FUNCIONES RE CURSIVAS  Se dice que una función es recursiva cuando el cuerpo de la función utiliza a la propia función. Dentro de una función recursiva suelen distinguirse dos partes:   -   Los casos base: Son aquellos que para su soluc...

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