Sinopsis

Este clásico manual sobre lenguajes formales, teoría de los automatismos y complejidad computacional ha sido actualizado a los conceptos teóricos actuales de forma directa y concisa con aplicaciones prácticas de cobertura creciente. Esta tercera edición ofrece a los estudiantes un estilo menos formal, a la vez proporciona el enfoque más accesible de la teoría de los automatismos existente, un tratamiento sólido de las pruebas constructivas, multitud de figuras y diagramas que ayudan a aclarar las ideas, así como símbolos que ayudan a resaltar los conceptos relacionados. Otra nueva característica de la presente edición es Gradience, que son unas prácticas en la Web, y una herramienta de evaluación. Cada capítulo contiene gran cantidad de ejercicios, e incluye problemas seleccionados de Gradience, para que los estudiantes adquieran una experiencia propia en el aprendizaje. | Los adelantos que ha sufrido esta materia desde 2002 hacen una casi obligatoria puesta al día, además en esta 3ª ed, se incluye un material complementario sin competencia que será un claro apoyo para los estudiantes dentro del marco de convergencia europea. www.aw.com/gradiance. |

Índice

1. Introducción a los autómatas. 2. Autómatas finitos. 3. Lenguajes y expresiones regulares. 4. Propiedades de los lenguajes regulares. 5. Lenguajes y gramáticas independientes del contexto. 6. Autómatas y filas. 7. Propiedades de los lenguajes independientes del contexto. 8. Introducción a las máquinas Turing. 9. Indecidibilidad. 10.Problemas intratables. 11.Otra clase de problemas. Índice