Introducción a la teoría de autómatas, lenguajes y computación / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.

CONTENIDO
1. Introducción a los autómatas 1
1.1. ¿Por qué estudiar la teoría de autómatas? 2
1.1.1. Introducción a los autómatas finitos 2
1.1.2. Representaciones estructurales 4
1.1.3. Autómatas y complejidad 4
1.2. Introducción a las demostraciones formales 5
1.2.1. Demostraciones deductivas 5
1.2.2. Reducción a definiciones 7
1.2.3. Otras formas de teoremas 8
1.2.4. Teoremas que parecen no ser proposiciones Si-entonces 11
1.3. Otras formas de demostración 11
1.3.1. Demostración de equivalencias entre conjuntos 12
1.3.2. La conversión contradictoria 12
1.3.3. Demostración por reducción al absurdo 14
1.3.4. Contraejemplos 15
1.4. Demostraciones inductivas 16
1.4.1. Inducciones sobre números enteros 16
1.4.2. Formas más generales de inducción sobre enteros 19
1.4.3. Inducciones estructurales 20
1.4.4. Inducciones mutuas 22
1.5. Conceptos fundamentales de la teoría de autómatas 24
1.5.1. Alfabetos 24
1.5.2. Cadenas de caracteres 24
1.5.3. Lenguajes 26
1.5.4. Problemas 27
1.6. Resumen del Capítulo 1 28
1.7. Referencias del Capítulo 1 30
2. Autómatas finitos 31
2.1. Descripción informal de autómata finito 31
2.1.1. Reglas básicas 32
2.1.2. El protocolo 32
2.1.3. Cómo permitir que el autómata ignore acciones 34
2.1.4. Un autómata para el sistema completo 35
2.1.5. Utilización del autómata producto para validar el protocolo 37
2.2. Autómata finito de terminista 37
2.2.1. Definición de autómata finito determinista 38
2.2.2. Cómo procesa cadenas un AFD 38
2.2.3. Notaciones más simples para los AFD 40
2.2.4. Extensión a cadenas de la función de transición 41
2.2.5. El lenguaje de un AFD 43
2.2.6. Ejercicios de la Sección 44
2.3. Autómatas finitos no deterministas 46
2.3.1. Punto de vista informal de los autómatas finitos no deterministas 46
2.3.2. Definición de autómata finito no determinista 48
2.3.3. Función de transición extendida 48
2.3.4. El lenguaje de un AFN 49
2.3.5. Equivalencia de autómatas finitos deterministas y no deterministas 51
2.3.6. Un caso desfavorable para la construcción de subconjuntos 54
2.3.7. Ejercicios de la Sección 2.3 56
2.4. Aplicación: búsqueda de texto 57
2.4.1. Búsqueda de cadenas en un texto 57
2.4.2. Autómatas finitos no deterministas para búsqueda de texto 58
2.4.3. Un AFD para reconocer un conjunto de palabras clave 59
2.4.4. Ejercicios de la Sección 2.4 61
2.5. Autómatas finitos con transiciones-E 61
2.5.1. Usos de las transiciones-E 61
2.5.2. Notación formal para un AFN-E 62
2.5.3. Clausuras respecto de epsilon 63
2.5.4. Transiciones y lenguajes extendidos para los AFN-E 64
2.5.5. Eliminación de las transiciones-E 65
2.5.6. Ejercicios de la Sección 2.5 68
2.6. Resumen del Capítulo 2 68
2.7. Referencias del Capítulo 2 69
3. Lenguajes y expresiones regulares 71
3.1. Expresiones regulares 71
3.1.1. Operadores de las expresiones regulares 72
3.1.2. Construcción de expresiones regulares 73
3.1.3. Precedencia de los operadores en las expresiones regulares 75
3.1.4. Ejercicios de la Sección 3.1 76
3.2. Autómatas finitos y expresiones regulares 77
3.2.1. De los AFD a las expresiones regulares 78
3.2.2. Conversión de un AFD en una expresión regular mediante la eliminación de estados 82
3.2.3. Conversión de expresiones regulares en autómatas 86
3.2.4. Ejercicios de la Sección 3.2 89
3.3. Aplicaciones de las expresiones regulares 92
3.3.1. Expresiones regulares en UNIX 92
3.3.2. Análisis léxico 93
3.3.3. Búsqueda de patrones en textos 95
3.3.4. Ejercicios de la Sección 3.3 96
3.4. Algebra de las expresiones regulares 96
3.4.1. Asociatividad y conmutatividad 97
3.4.2. Elemento identidad y elemento nulo 98
3.4.3. Leyes distributivas 98
3.4.4. Ley de idempotencia 99
3.4.5. Leyes relativas a las clausuras 99
3.4.6. Descubrimiento de propiedades de las expresiones regulares 100
3.4.7. Comprobación de una propiedad algebraica de las expresiones regulares 101
3.4.8. Ejercicios de la Sección 3.4 102
3.5. Resumen del Capítulo 3 103
3.6. Referencias del Capítulo 3 104
4. Propiedades de los lenguajes regulares 105
4.1. Cómo demostrar que un lenguaje no es regular 105
4.1.1. El lema de bombeo para los lenguajes regulares 106
4.1.2. Aplicaciones del lema de bombeo 108
4.1.3. Ejercicios de la Sección 4.1 109
4.2 Propiedades de clausura de los lenguajes regulares 110
4.2.1. Clausura de lenguajes regulares para las operaciones booleanas 110
4.2.2. Reflexión 115
4.2.3. Homomorfismo 117
4.2.4. Homomorfismo inverso 118
4.2.5. Ejercicios de la Sección 4.2 122
4.3. Propiedades de decisión de los lenguajes regulares 125
4.3.1. Conversión entre representaciones 126
4.3.2. Cómo comprobar la pertenencia a un lenguaje regular 129
4.3.3. Ejercicios de la Sección 4.3 129
4.4. Equivalencia y minimización de autómatas 129
4.4.1. Cómo comprobar la equivalencia de estados 130
4.4.2. Cómo comprobar la equivalencia de lenguajes regulares 133
4.4.3. Minimización de un AFD 134
4.4.4. ¿Por qué el AFD minimizado no se puede reducir aún más 137
4.4.5. Ejercicios de la Sección 4.4 138
4.5. Resumen del Capítulo 4 139
4.6. Referencias del Capítulo 4 140
5. Lenguajes y gramáticas independientes del contexto 143
5.1. Gramáticas independientes del contexto 144
5.1.1. Un ejemplo informal 144
5.1.2. Definición de las gramáticas independientes del contexto 145
5.1.3. Derivaciones utilizando una gramática 146
5.1.4. Derivaciones izquierda y derecha 149
5.1.5. Lenguaje de una gramática 150
5.1.6. Formas sentenciales 151
5.1.7. Ejercicios de la Sección 5.1 152
5.2. Arboles de derivación 154
5.2.1. Construcción de los árboles de derivación 154
5.2.2. Resultado de un árbol de derivación 155
5.2.3. Inferencia, derivaciones y árboles de derivación 156
5.2.4. De las inferencias a los árboles 158
5.2.5. De los árboles a las derivaciones 159
5.2.6. De las derivaciones a las inferencias recursivas 162
5.2.7. Ejercicios de la Sección 5.2 163
5.3. Aplicaciones de las gramáticas independientes del contexto 164
5.3.1. Analizadores sintácticos 164
5.3.2. El generador de analizadores YACC 166
5.3.3. Lenguajes de marcado 167
5.3.4. XML y las DTD 169
5.3.5. Ejercicios de la Sección 5.3 174
5.4. Ambiguedad en gramáticas y lenguajes 175
5.4.1. Gramáticas ambiguas 175
5.4.2. Eliminación de la ambiguedad de las gramáticas 177
5.4.3. Derivaciones más a la izquierda como forma de expresar la ambiguedad 180
5.4.4. Ambiguedad inherente 181
5.4.5. Ejercicios de la Sección 5.4 183
5.5. Resumen del Capítulo 5 184
5.6. Referencias del Capítulo 5 185
6. Autómatas a pila 187
6.1. Definición de autómata a pila 187
6.1.1. Introducción informal 187
6.1.2. Definición formal de autómata a pila 189
6.1.3. Notación gráfica para los autómatas a pila 190
6.1.4. Descripciones instantáneas de un autómata a pila 191
6.1.5. Ejercicios de la Sección 6.1 194
6.2. Lenguajes de un autómata a pila 195
6.2.1. Aceptación por estado final 196
6.2.2. Aceptación por pila vacía 197
6.2.3. De pila vacía a estado final 197
6.2.4. Del estado final a la pila vacía 200
6.2.5. Ejercicios de la Sección 6.2 202
6.3. Equivalencia entre autómatas a pila y gramáticas independientes del contexto 203
6.3.1. De las gramáticas a los autómatas a pila 203
6.3.2. De los autómatas a pila a las gramáticas 206
6.3.3. Ejercicios de la Sección 6.3 210
6.4. Autómata a pila determinista 211
6.4.1. Definición de autómata a pila determinista 211
6.4.2. Lenguajes regulares y autómatas a pila deterministas 211
6.4.3. Autómatas a pila deterministas y lenguajes independientes del contexto 213
6.4.4. Autómatas a pila deterministas y gramáticas ambiguas 213
6.4.5. Ejercicios de la Sección 6.4 214
6.5. Resumen del Capítulo 6 215
6.6. Referencias del Capítulo 6 216
7. Propiedades de los lenguajes independientes del contexto 217
7.1. Formas normales para las gramáticas independientes del contexto 217
7.1.1. Eliminación de símbolos inútiles 218
7.1.2. Cálculo de símbolos generadores y alcanzables 219
7.1.3. Eliminación de producciones-E 221
7.1.4. Eliminación de las producciones unitarias 224
7.1.5. Forma normal de Chomsky 227
7.1.6. Ejercicios de la Sección 7.1 231
7.2. El lema de bombeo para lenguajes independientes del contexto 233
7.2.1. El tamaño de los árboles de derivación 234
7.2.2. Enunciado del lema de bombeo 234
7.2.3. Aplicaciones del lema de bombeo para los LIC 236
7.2.4. Ejercicios de la Sección 7.2 239
7.3. Propiedades de clausura de los lenguajes independientes del contexto 240
7.3.1. Sustituciones 240
7.3.2. Aplicaciones del teorema de sustitución 242
7.3.3. Reflexión 243
7.3.4. Intersección con un lenguaje regular 243
7.3.5. Homomorfismo inverso 247
7.3.6. Ejercicios de la Sección 7.3 249
7.4. Propiedades de decisión de los LIC 251
7.4.1. Complejidad de la conversión entre gramáticas GIC y autómatas a pila 251
7.4.2. Tiempo de ejecución de la conversión a la forma normal de Chomsky 252
7.4.3. Comprobación de si un LIC está vacío 253
7.4.4. Comprobación de la pertenencia a un LIC 255
7.4.5. Anticipo de los problemas indecidibles de los LIC 258
7.4.6. Ejercicios de la Sección 7.4 258
7.5. Resumen del Capítulo 7 259
7.6. Referencias del Capítulo 7 259
8. Introducción a las máquinas de Turing 261
8.1. Problemas que las computadoras no pueden resolver 261
8.1.1. Programas que escriben "Hola, mundo" 262
8.1.2. Comprobador hipotético de "hola, mundo" 263
8.1.3. Reducción de un problema a otro 266
8.1.4. Ejercicios de la Sección 8.1 269
8.2. La máquina de Turing 269
8.2.1. El intento de decidir todas las cuestiones matemáticas 270
8.2.2. Notación para la máquina de Turing 270
8.2.3. Descripciones instantáneas de las máquinas de Turing 272
8.2.4. Diagramas de transición para las máquinas de Turing 274
8.2.5. El lenguaje de una máquina de Turing 277
8.2.6. Máquinas de Turing y parada 278
8.2.7. Ejercicios de la Sección 8.2 279
8.3. Técnicas de programación para las máquinas de Turing 280
8.3.1. Almacenamiento en el estado 280
8.3.2. Pistas múltiples 281
8.3.3. Subrutinas 283
8.3.4. Ejercicios de la Sección 8.3 285
8.4. Extensiones de la máquina de Turing básica 285
8.4.1. Máquina de Turing de varias cintas 286
8.4.2. Equivalencia entre las MT de una sola cinta y de varias cintas 287
8.4.3. Tiempo de ejecución en la construcción que pasa de muchas cintas a una 287
8.4.4. Máquinas de Turing no deterministas 289
8.4.5. Ejercicios de la Sección 8.4 291
8.5. Máquinas de Turing restringidas 293
8.5.1. Máquinas de Turing con cintas semi-infinitas 294
8.5.2. Máquinas con varias pilas 296
8.5.3. Máquinas contadoras 298
8.5.4. La potencia de las máquinas contadoras 299
8.5.5. Ejercicios de la Sección 8.5 301
8.6. Máquinas de Turing y computadoras 301
8.6.1. Simulación de una máquina de Turing mediante una computadora 302
8.6.2. Simulación de una computadora mediante un máquina de Turing 303
8.6.3. Comparación de los tiempos de ejecución de las computadoras y las máquinas de Turing 306
8.7. Resumen del Capítulo 8 309
8.8. Referencias del Capítulo 8 310
9. Indecidibilidad 313
9.1. Lenguaje no recursivamente enumerable 314
9.1.1. Enumeración de cadenas binarias 314
9.1.2. Códigos para las máquinas de Turing 314
9.1.3. El lenguaje de diagonalización 316
9.1.4. Demostración de que L (sub d) no es recursivamente enumerable 317
9.1.5. Ejercicios de la Sección 9.1 317
9.2. Un problema indecidible recursivamente enumerable 318
9.2.1. Lenguajes recursivos 318
9.2.2. Complementarios de los lenguajes recursivos y RE 319
9.2.3. El lenguaje universal 321
9.2.4. Indecidibilidad del lenguaje universal 323
9.2.5. Ejercicios de la Sección 9.2 324
9.3. Problemas indecidibles para las máquinas de Turing 326
9.3.1. Reducciones 326
9.3.2. Máquinas de Turing que aceptan el lenguaje vacío 327
9.3.3. Teorema de Rice y propiedades de los lenguajes RE 330
9.3.4. Problemas sobre especificaciones de las máquinas de Turing 332
9.3.5. Ejercicios de la Sección 9.3 332
9.4. Problema de correspondencia de Post 334
9.4.1. Definición del problema de la correspondencia de Post 334
9.4.2. El PCP "modificado" 336
9.4.3. Finalización de la demostración de la indecibilidad del PCP 338
9.4.4. Ejercicios de la Sección 9.4 343
9.5. Otros problemas indecidibles 343
9.5.1. Problemas sobre programas 344
9.5.2. Indecidibilidad de la ambiguedad de las GIC 344
9.5.3. Complementario de un lenguaje de lista 346
9.5.4. Ejercicios de la Sección 9.5 348
9.6. Resumen del Capítulo 9 349
9.7. Referencias del Capítulo 9 349
10. Problemas intratables 351
10.1. Las clases P y NP 352
10.1.1. Problemas resolubles en tiempo polinómico 352
10.1.2. Ejemplo: algoritmo de Kruskal 353
10.1.3. Tiempo polinómico no determinista 356
10.1.4. Ejemplo de NP: el problema del viajante de comercio 356
10.1.5. Reducciones en tiempo polinómico 357
10.1.6. Problemas NP-completos 358
10.1.7. Ejercicios de la Sección 10.1 360
10.2. Un problema NP-completo 362
10.2.1. El problema de la satisfacibilidad 362
10.2.2. Representación de problemas SAT 363
10.2.3. El problema SAT es NP-Completo 364
10.2.4. Ejercicios de la Sección 10.2 369
10.3. Problema de la satisfacibilidad restringido 370
10.3.1. Formas normales de las expresiones booleanas 370
10.3.2. Conversión de expresiones a la FNC 371
10.3.3. CSAT es NP-Completo 373
10.3.4. 3SAT es NP-completo 378
10.3.5. Ejercicios de la Sección 10.3 379
10.4. Otros problemas NP-completos 379
10.4.1. Descripción de problemas NP-completos 380
10.4.2. El problema de los conjuntos independientes 380
10.4.3. El problema del recubrimiento de nodos 384
10.4.4. El problema del circuito hamiltoniano orientado 385
10.4.5. Circuitos hamiltonianos no orientados y el PVC 390
10.4.6. Resumen de los problemas NP-completos 391
10.4.7. Ejercicios de la Sección 10.4 392
10.5. Resumen del Capítulo 10 395
10.6. Referencias del Capítulo 10 396
11. Otras clases de problemas 399
11.1. Complementarios de los lenguajes de NP 400
11.1.1. La clase de lenguajes co-NP 400
11.1.2. Problemas NP-completos y Co-NP 401
11.1.3. Ejercicios de la Sección 11.1 402
11.2. Problemas resolubles en espacio polinómico 402
11.2.1. Máquinas de Turing con espacio polinómico 403
11.2.2. Relaciones de PS y NPS con las clases definidas anteriormente 403
11.2.3. Espacio polinómico determinista y no determinista 405
11.3. Un problema que es completo para PS 407
11.3.1. Problemas PS-completos 407
11.3.2. Fórmulas booleanas con cuantificadores 408
11.3.3. Evaluación de fórmulas booleanas con cuantificadores 409
11.3.4. El problema FBC es PS-completo 410
11.3.5. Ejercicios de la Sección 11.3 414
11.4. Clases de lenguajes basadas en la aleatorización 415
11.4.1. Quicksort: ejemplo de un algoritmo con aleatoriedad 415
11.4.2. Modelo de la máquina de Turing con aleatoriedad 416
11.4.3. El lenguaje de una máquina de Turing con aleatoriedad 417
11.4.4. La clase RP 419
11.4.5. Reconocimiento de los lenguajes de RP 421
11.4.6. La clase ZPP 422
11.4.7. Relaciones entre RP y ZPP 422
11.4.8. Relaciones de las clases P y NP 423
11.5. La complejidad de la prueba de primalidad 424
11.5.1. La importancia de la prueba de primalidad 425
11.5.2. Introducción a la aritmética modular 426
11.5.3. Complejidad de los cálculos en aritmética modular 428
11.5.4. Prueba de primalidad aleatorio-polinómica 429
11.5.5. Pruebas de primalidad no deterministas 430
11.5.6. Ejercicios de la Sección 11.5 432
11.6. Resumen del Capítulo 11 433
11.7. Referencias del Capítulo 11 434