Teoría de autómatas, lenguajes y computación /
John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman
- 3° Ed.
- 440 páginas ; 25 cm.
Factura Educativa
1.-Introduccion a las automatas: - ¿Por que estudiar la toeria de automatas? -Introduccion a las demostraciones formales - Otras formas de demostracion - Demostraciones inductivas - Conceptos fundamentales de la teoria de automatas 2.-Automatas finitos: - Descripcion informal de automata finito - Automata finito determinista - Automatas finitos no deterministas - Aplicacion: busqueda de texto - Automatas finitos con transiciones -e 3.-Lenguajes y expresiones regulares: - Expresiones regulares - Automatas finitos y expresiones regulares - Aplicaciones de las expresiones regulares -Algebra de las expresiones regulares 4.-Propiedades de los lenguajes regulares: - Como demostrar que un lenguaje no es regular - Propiedades de clausura de los lenguajes regulares - Propiedades de decision de los lenguajes regulares -Equivalencia y minimizacion de automatas 5.-Lenguajes y gramaticas independientes del contexto: - Gramaticas independientes del contexto - Arboles de derivacion - Aplicaciones de las gramaticas independientes del contexto - Ambiguedad en gramatica y lenguajes -.-Automatas a pila: - Definicion de automata a pila - Lenguajes de un automata a pila - Equivalencia entre automatas a pila y gramaticas independientes del contexto - Automata a pila determinista 7.-Propiedades de los lenguajes independientes del contexto: - Formas normales para las gramaticas -El lema de bombeo para lenguaje -Propiedades de clausura de los lenguajes independientes del contexto - Propiedades de decision de las LIC 8.-Introduccion a las maquinas de Turing: - Problemas que las computadoras no pueden resolver -La maquina de Turing - Tecnicas de programacion para las maquinas de Turing - Extensiones de la maquina de Turing basica - Maquinas de turing restringidas - Maquinas de turing computadoras 9.-Indecidibilidad - Lenguaje no recursivamente enumerable - Un problema indecidible recursivamente enumerable - Problemas indecidibles para las maquinas de Turing - Problema de correspondencia de Post - Otros probleas indecidibles 10.-Problemas intratables: - Las clases P y NP - Un problema NP - completo - Problema de la satisfacibilidad restringido - Otros problemas Np-completos 11.-Otras clases de problemas: - Complementarios de los lenguajes de NP - Problemas resolubles en espacio polinomico - Un problema que es completo para PS - Clases de lenguajes basadas en la aleatorizacion -La complejidad de la prueba de primalidad