Información General

• Autores: Enrique Alfonseca Cubero , Manuel Alfonseca Moreno , Roberto Moriyón Salomón
• Editores: McGraw-Hill Interamericana de España
• Año de publicación: 2007
• País: España
• Idioma: español
• ISBN: 84-481-5637-4, 978-84-481-5637-4
• Texto completo no disponible (Saber más ...)

Otros catálogos

• Red de Bibliotecas Universitarias (REBIUN)

Índice

• 1 Máquinas, lenguajes y problemas. 1-18
   1.1 Breve historia de las máquinas. 1-5
   1.2 Lenguajes y gramáticas. 5-7
  1.3 Desarrollo del libro 7-9
  1.4 Algunas definiciones básicas 9-17
  1.5 Ejercicios 17-18
  2 Máquinas de Turing 19-70
   2.1 Introducción a las máquinas de Turing 19-34
   2.2 Equivalencias entre máquinas de Turing 34-53
   2.3 Máquinas de Turing no deterministas 53-59
   2.4 Submáquinas de Turing 59-65
   2.5 Ejercicios 65-70
  3 Autómatas finitos 71-116
   3.1 Autómatas finitos deterministas 71-80
   3.2 Minimización de autómatas finitos deterministas 80-90
   3.3 Autómatas finitos no deterministas 90-102
   3.4 Equivalencias entre autómatas finitos 102-106
   3.5 Algunos teoremas sobre autómatas finitos 106-109
   3.6 Máquinas secuenciales 109-115
   3.7 Ejercicios 115-116
  4 Autómatas a pila 117-145
   4.1 Autómatas a pila deterministas 121-133
   4.2 Autómatas a pila no deterministas 133-134
   4.3 Otros tipos de autómatas a pila 140-142
   4.4 Ejercicios 142-144
  5 Gramáticas 145-174
   5.1 Derivación 147-149
   5.2 Definición formal de gramática 149-153
   5.3 Tipos de gramáticas de Chomsky 153-160
   5.4 Árboles de derivación 160-165
   5.5 Gramáticas limpias y bien formadas. 165-171
   5.6 Ejercicios. 171-174
  6 Gramáticas y máquinas: tipos 0 y 1 175-218
   6.1 Gramáticas de tipo 0 y máquinas de Turing 177-195
   6.2 Funciones recursivas 195-210
   6.3 Gramáticas de tipo 1 y autómatas lineales acotados 210-216
   6.4 Ejercicios 216-218
  7 Lenguajes regulares 219-248
   7.1 Autómata asociado a una gramática de tipo 3 219-222
   7.2 Expresiones regulares 222-237
   7.3 Resumen de las equivalencias 237-239
   7.4 Lema de bombeo de los lenguajes regulares 239-242
   7.5 Propiedades de los lenguajes regulares 242-243
   7.6 Ejercicios 243-248
  8 Lenguajes independientes del contexto 249-276
   8.1 Gramáticas de tipo 2 y autómatas a pila 250-257
   8.2 Formas normales de las gramáticas de tipo 2 257-265
   8.3 Lema de bombeo de los lenguajes independientes del contexto 265-269
   8.4 Propiedades de los lenguajes independientes del contexto 269-274
   8.5 Ejercicios 274-276
  9 Computabilidad y complejidad 277-314
   9.1 La máquina de Turing universal 278-288
   9.2 Problemas indecidibles 288-294
   9.3 Problemas de los problemas 294-314
   9.4 Ejercicios 314
  10 Otras máquinas y gramáticas 315-346
   10.1 Autómatas finitos probabilísticos 316-320
   10.2 Autómatas celulares 320-324
   10.3 Celulas de McCullogh y Pitts 324-332
   10.4 Gramáticas de lindenmayer 332-346
  11 Sistemas avanzados de cómputo 347-373
   11.1 Computación con membranas: sistemas P 347-358
   11.2 Computación con ADN 358-366
   11.3 Computación cuántica 366-372
  A Conceptos matemáticos utilizados 373-388
   A.1 Introducción a la lógica proposicional 373-379
   A.2 Teoría de relaciones 379-383
   A.3 Conjuntos numerables y no numerables 383-386
   A.4 Ejercicios 386-388
  Bibliografía 389-393
  Índice alfabético 393-400