Lenguajes, gramáticas y autómatas : un enfoque práctico / Pedro Isasi Viñuela, Paloma Martínez Fernández, Daniel Borrajo Millán.

CONTENIDO
1 Introducción 1
1.1 Lenguajes, Gramáticas y Autómatas 1
1.2 Estructura del libro 5
1.3 Notaciones 6
2 Lenguajes y Gramáticas Formales 7
2.1 Lenguajes 7
2.1.1 Definiciones básicas 7
2.1.2 Operaciones con palabras 8
2.1.3 Operaciones con lenguajes 9
2.1.4 Otras definiciones 11
2.2 Gramáticas formales 13
2.2.1 Definiciones 13
2.2.2 Tipos de Gramáticas 16
2.2.3 Árboles de derivación 19
2.2.4 Ambiguedad 20
2.2.5 Recursividad 21
2.2.6 Factorización a izquierdas 25
Ejercicios 27
3 Gramáticas Regulares y Autómatas Finitos 43
3.1 Gramáticas regulares 43
3.2 Máquinas Secuenciales 46
3.2.1 Definición 46
3.2.2 Representación 49
3.2.3 Extensión a palabras de la entrada y salida 51
3.2.4 Equivalencia de Máquinas Secuenciales 55
3.2.5 Equivalencia de Máquina de Mealy y Máquina de Moore 61
3.3 Autómatas Finitos Deterministas (AFD) 63
3.3.1 Definición 63
3.3.2 Representación de un AFD 65
3.3.3 Conceptos relativos a AFDs 66
3.3.4 Equivalencia de AFD 68
3.4 Autómatas Finitos No Deterministas (AFND) 75
3.4.1 Definición 75
3.4.2 Representación 76
3.4.3 Conceptos asociados a AFNDs 77
3.4.4 Autómata Finito asociado a una G3 81
3.5 Expresiones regulares (ER) 83
3.5.1 Definiciones 83
3.5.2 Teoremas de Kleene 85
3.6 Autómatas de Células de McCulloch-Pitts 97
3.6.1 Definición 97
3.6.2 Representación 98
3.6.3 Construcción de un AF equivalente 101
3.6.4 Construcción de un Autómata de Células equivalente a un AF 106
3.7 Autómatas probabilísticos 107
3.7.1 Definición 108
3.7.2 Matrices de probabilidad de transición 108
3.7.3 Vectores de estados 109
3.7.4 Lenguaje aceptado por un AFP 111
3.7.5 AF como AFP 113
Ejercicios 115
4 Gramáticas Independientes del Contexto y Autómatas a Pila 237
4.1 Gramáticas Independientes del Contexto 237
4.1.1 Definiciones 237
4.1.2 Forma Normal de Chomsky (FNC) 242
4.1.3 Forma Normal de Greibach (FNG) 246
4.2 Autómatas a Pila (AP) 248
4.2.1 Definición 248
4.2.2 Movimientos 251
4.2.3 Descripción instantánea 254
4.2.4 Autómatas a Pila Deterministas 255
4.2.5 Lenguaje aceptado por un AP 256
4.2.6 Autómatas a Pila y Gramáticas de tipo 2 257
Ejercicios 263
5 Gramáticas y autómatas generales 321
5.1 Máquinas de Turing 321
5.1.1 Definición 321
5.1.2 Movimiento 323
5.1.3 Lenguaje reconocido por una Máquina de Turing 326
5.1.4 Variantes de las Máquinas de Turing 326
5.1.5 Máquina de Turing Universal (MTU) 327
5.1.6 Máquinas de Turing y computación 329
5.2 Autómatas Linealmente Acotados 330
Ejercicios 331
6 Aplicaciones 343
6.1 Construcción de compiladores 343
6.1.1 Analizador Léxico 346
6.1.2 Analizador Sintáctico 351
6.2 Análisis del lenguaje natural 357
6.3 Aplicaciones de Control 368
6.4 Más aplicaciones 372