Introducción a la teoría de autómatas, lenguajes y computación
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Libro |
| Lenguaje: | Español Inglés |
| Publicado: |
México D. F. :
CECSA,
1998.
|
| Edición: | 1a ed. |
| Materias: | |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 05086nam a22004097a 4500 | ||
|---|---|---|---|
| 003 | AR-BaUNH | ||
| 005 | 20251001062828.0 | ||
| 008 | 230901b |||||||| |||| 00| 0 spa d | ||
| 020 | |a 9789682612225 | ||
| 040 | |a AR-BaUNH |b spa |c AR-BaUNH |d AR-BaUNH |e aacr | ||
| 041 | 1 | |a spa |h eng | |
| 082 | 1 | |a 003 | |
| 100 | 1 | |9 7499 |a Hopcroft, John E. | |
| 100 | 1 | |9 7500 |a Ullman, Jeffrey D. | |
| 245 | 1 | |a Introducción a la teoría de autómatas, lenguajes y computación | |
| 250 | |a 1a ed. |b 4a reimp. | ||
| 260 | |a México D. F. : |b CECSA, |c 1998. | ||
| 300 | |a x, 447 p. : |b il. byn., tb., gr. ; |c 23 cm. | ||
| 505 | |t Capítulo 1 : Preliminares -- |a Cadenas, alfabetos y lenguajes -- Grafos y árboles -- Pruebas inductivas -- Notación de conjuntos -- Relaciones -- Sinopsis del libro -- | ||
| 505 | |t Capítulo 2: Autómatas finitos y expresiones regulares -- |a Sistemas de estados finitos -- Definiciones básicas -- Autómatas finitos no determinísticos -- Autómatas finitos con movimientos-e -- Expresiones regulares -- Autómatas finitos de dos direcciones -- Autómatas finitos con salida -- Aplicaciones de los autómatas finitos -- | ||
| 505 | |t Capítulo 3: Propiedades de los conjuntos regulares -- |a El lema de sondeo para conjuntos regulares -- Propiedades de cerradura para conjuntos regulares -- Algoritmos de decisión para conjuntos regulares -- Teorema de Myhill-Nerode y minimización de autómatas finitos -- | ||
| 505 | |t Capítulo 4: Gramáticas libres de contexto -- |a Motivación e introducción -- Gramáticas libres de contexto -- Arboles de derivación -- Simplificación de gramáticas libres de contexto -- Forma normal de Chomsky -- Forma normal de Greibach -- Existencia de lenguajes libres de contexto inherentemente ambiguos -- | ||
| 505 | |t Capítulo 5: Automatas de apilamiento -- |a Descripción informal -- Definiciones -- Autómatas de apilamiento y lenguajes libres de contexto -- | ||
| 505 | |t Capítulo 6: Propiedades de los lenguajes libres de contexto -- |a Lema de sondeo para CFLs -- Propiedades de cerradura para CFLs -- Algoritmos de decisión para CFLs -- | ||
| 505 | |t Capítulo 7: Máquinas de Turing -- |a Introducción -- Modelo de la máquina de Turing -- Lenguajes y funciones computables -- Técnicas para la construcción de máquinas de Turing -- Modificaciones de las máquinas de Turing -- Hipótesis de Church -- Máquinas de Turing como enumeradores -- Máquinas de Turing restringidas equivalentes al modelo básico -- | ||
| 505 | |t Capítulo 8: Irresolubilidad -- |a Problemas -- Propiedades de los lenguajes recursivos y numerables de manera recursiva -- Máquinas de Turing universales y un problema irresoluble -- Teorema de Rice y algunos otros problemas irresolubles -- Irresolubilidad del problema de correspondencia de Post -- Cálculos válidos y no válidos de TMs: una herramienta para probar problemas CFL irresolubles -- Teorema de Greibach -- Introducción a la teoría de las funciones recursivas -- Cálculos de oráculo -- | ||
| 505 | |t Capítulo 9: La jerarquía de Chomsky -- |a Gramáticas regulares -- Gramáticas no restringidas -- Lenguajes sensibles al contexto -- Relaciones entre tipos de lenguajes -- | ||
| 505 | |t Capítulo 10: Lengnajes deterministicos libres de contexto -- |a Formas normales para DPDAs -- Cerradura de los DCFLs con respecto a la complementación -- Máquinas de predicción -- Propiedades de cerradura adicionales de los DCFLA -- Propiedades de decisión de los DCFLs -- Gramáticas LR(0) -- Gramáticas LR(0) y los DPDAs -- Gramáticas LR(k) -- | ||
| 505 | |t Capítulo 11: Propiedades de cerradura de familias de lenguajes -- |a Tríos y tríos completos -- Transformaciones de máquinas secuenciales generalizadas -- Otras propiedades de cerradura para trios -- Familias abstractas de lenguajes -- Independencia de las operaciones AFL -- Resumen -- | ||
| 505 | |t Capítulo 12: Teoría de complejidad computacional -- |a Definiciones -- Aceleración lineal, compresión de cinta y reducciones en el número de cintas -- Teoremas de jerarquías -- Relaciones entre medidas de complejidad -- Lemas de traslación y las jerarquías no determinísticas -- Propiedades de las medidas de complejidad general: teoremas de espacio, aceleración y unión -- Teoría de complejidad axiomática -- | ||
| 505 | |t Capítulo 13: Problemas no tratables -- |a Tiempo y espacio polinomiales -- Algunos problemas NP-completos -- La clase co-NP -- Problemas ESPACIOP completos -- Problemas completos para y ESPACION (log n) -- Algunos problemas demostrablemente no tratables -- La cuestión para las máquinas de Turing con oráculos: limites en nuestra capacidad para determinar si P = NP -- | ||
| 505 | |t Capítulo 14: Caracteristicas principales de otras clases de lenguaje -- |a Autómatas de presión auxiliares -- Autómatas de pila -- Lenguajes indexados -- Sistemas de desarrollo -- | ||
| 650 | 0 | |9 2816 |a COMPUTACIÓN | |
| 650 | 7 | |a LENGUAJES DE PROGRAMACIÓN |2 Vocabulario General de la Biblioteca Nacional de Maestros |9 4665 | |
| 900 | |a Carolina |b Carolina | ||
| 942 | |2 ddc |c B.O. | ||
| 999 | |c 5121 |d 5123 | ||