Introducción a la teoría de autómatas lenguajes y computación [texto impreso] /
John E. Hopcroft ;
Rajeev Motwani ;
Jeffrey D. Ullman . - 3a.ed. . -
Boston : Pearson, 2008 . - p. xvi, 440 p.
ISBN : 978-84-7829-088-8
Idioma : Español
| Temas: | COMPUTACION
INFORMATICA
LENGUAJES DE PROGRAMACION
LOGICA MATEMATICA
MATEMATICAS
TEORIA DE AUTOMATAS
TEORIA DE MAQUINAS
|
| Clasificación: | 511.3 |
| Nota de contenido: | Introducción a los autómatas -- ¿Por qué estudiar la teoría de los autómatas? -- Introducción a las demostraciones formales -- Otras formas de demostración -- Demostraciones inductivas -- Conceptos fundamentales de la teoría de los autómatas -- Autómatas finitos -- Descripción informal de autómatas finitos -- Autómata finito determinista -- Autómatas finitos no deterministas -- Aplicación: búsqueda de texto -- Autómatas finitos con transiciones ε -- Lenguajes y expresiones regulares -- Expresiones regulares -- Autómatas finitos y expresiones regulares -- Aplicaciones de las expresiones regulares -- Álgebra de las expresiones regulares -- Propiedades de los lenguajes regulares -- Cómo demostrar que un lenguaje no es regular -- Propiedades de clausura de los lenguajes regulares -- Propiedades de decisión de los lenguajes regulares -- Equivalencia y minimización de autómatas -- Lenguajes y gramáticas independientes del contexto -- Gramáticas independientes del contexto -- Árboles de derivación -- Aplicaciones de las gramáticas independientes del contexto -- Ambigüedad en gramáticas y lenguajes -- Autómatas a pila -- Definición de autómata a pila -- Lenguajes de un autómata a pila -- Equivalencia entre autómata a pila y gramáticas independientes del contexto -- Autómata a pila determinista -- Propiedades de los lenguajes independientes del contexto -- Formas normales para las gramáticas independientes del contexto -- El lema de bombeo para los lenguajes independientes del contexto -- Propiedades de clausura de los lenguajes independientes del contexto -- Propiedades de decisión de los LIC -- Introducción a las máquinas de Turing -- Problemas que las computadoras no pueden resolver -- La máquina de Turing -- Técnicas de programación para las máquinas de Turing -- Extensiones de la máquina de Turing básica -- Máquinas de Turing restringidas -- Máquinas de Turing y computadoras -- Indecidibilidad -- Lenguaje no recursivamente enumerable -- Un problema indecidible recursivamente enumerable -- Problemas indecidibles para las máquinas de Turing -- Problema de correspondencia de Post -- Otros problemas indecidibles -- Problemas intratables -- Las clases P y NP -- Un problema NP-completo -- Problema de la satisfacibilidad restringido -- Otros problemas NP-completos -- Otras clases de problemas -- Complementarios de los lenguajes NP -- Problemas resolubles en espacio polinómico -- Un problema que es completo para PSPACE -- Clases de lenguajes basadas en la aleatorización -- La complejidad de la prueba de primalidad -- Índice alfabético. |
| Enlace permanente a este registro: | https://opac.um.edu.uy/index.php?lvl=notice_display&id=84364 |
Introducción a la teoría de autómatas lenguajes y computación
