Lenguajes formales y teoría de autómatas finitos. Fundamentos para la creación de un traductor

Prólogo     

1. Conceptos básicos     

1.1 Componentes léxicos o tokens     
1.2 Alfabetos     
1.3 Cadena     
1.4 Lenguaje     

1.5 Operaciones con cadenas
1.5.1. Concatenación de cadenas     
1.5.2. Potencia de una cadena     
1.5.3. Longitud de una cadena     
1.5.4. Inverso de una cadena     
1.5.5. Subcadenas, sufijos y prefijos     

1.6. Operaciones con lenguajes     
1.6.1. Concatenación de lenguajes     
1.6.2. Potencia de un lenguaje     
1.6.3. Cerradura de Kleene (0 ó más casos)     
1.6.4. Cerradura positiva (1 ó más casos)     
1.6.5. Cerradura (de 0 ó 1 caso)     

1.7. Propiedades de las cerraduras de los lenguajes regulares     
1.8. Ejercicios resueltos     
1.9. Ejercicios propuestos     

2. Lenguajes regulares y expresiones regulares     

2.1. Clasificación de los lenguajes     
2.2. Lenguajes regulares     
2.2.1. Definición formal     
2.2.2. Lema de bombeo     
2.2.2.1. Demostración de que un lenguaje no es regular     
2.2.3. Propiedades de las cerraduras     
2.2.4. Homomorfismo     

2.3. Expresiones regulares     
2.3.1. Definición formal de expresión regular     
2.3.2. Propiedades de las expresiones regulares     
2.3.3. Simplificación de expresiones regulares     
2.3.4. Expresiones regulares y patrones     

2.4. Definiciones regulares     
2.4.1. La definición regular como concepto fundamental en el proceso del análisis léxico     2.4.2. Construcción de definiciones regulares a partir de un patrón     
2.5. Ejercicios propuestos     
2.6. Ejercicios propuestos de mayor complejidad     

3. Diagramas de transición y autómatas finitos

3.1. Diagramas de transición     
3.1.1. Estructura de un diagrama de transición     
3.1.2. Operaciones básicas     
3.1.2.1. Concatenación     
3.1.2.2. Unión
3.1.2.3. Cerradura de Kleene     
3.1.2.4. Cerradura positiva     
3.1.2.5. Cerradura de O ó I caso     
3.1.3. Ejemplos de diagrama de transición     

3.2. Autómatas finitos     
3.2.1. Autómatas finitos determinísticos (AFD)     
3.2.1.1. Definición formal
3.2.1.2. Función de transición extendida 5"     
3.2.1.3. Función de transición extendida     
3.2.1.4. Ejemplo (paso de un AFD a una expresión regular)     
3.2.2. Reconocimiento de cadenas en un AF     

3.2.3. Autómatas finitos no determinísticos AFN     
3.2.3.1. Definición formal     
3.2.3.2. Características de los AFN     
3.2.3.3. Función de transición extendida
3.2.3.4. Definición formal (reconocimiento de una cadena por un AFN)     
3.2.3.5. Aceptación de un lenguaje por AFN     

3.2.4. Paso de un AFN a un AFD - evaluación perezosa     
3.2.5. Conversión AFN-A a un AFD     
3.2.6. Aceptación de un lenguaje por un AFN
3.2.7. Diferencia conceptual entre un AFD y un AFN     
3.2.8. Reconocimiento de cadenas en un autómata finito (descripción instantánea)     
3.2.9. Conversión de una expresión regular a un AFN (método de Thompson)     
3.2.10. Conversión de un AFN a un AFD no óptimo (método de subconjunto)     
3.2.11. Conversión de una expresión regular a un AFD óptimo (estados significativos)     
3.3. Ejercicios propuestos     

4. Lenguajes y tipos de gramáticas     

4.1. Gramática     
4.2. Tipos de gramática
4.2.1. GSR tipo O: gramática sin restricciones tipo 0     
4.2.2. GCSP: gramática de contexto sensitivo puro     
4.2.3. GCS tipo 1: gramática de contexto sensitivo tipo 1     
4.2.4. GLCP: gramática libre de contexto puro     
4.2.5. GLC tipo 2: gramática libre de contexto     

4.2.6. GLD tipo 3: gramática lineal derecha tipo 3     
4.2.6.1. Lema de equivalencia entre un DFA y una GLD tipo 3     
4.2.7. Forma normal de Chomsky para GIC     
4.2.7.1. Eliminación de símbolos inútiles     
4.2.7.2. Eliminación de producciones con A     
4.2.7.3. Eliminación de producciones unitarias     
4.2.7.3.1 Mecanismo para eliminar producciones unitarias     
4.2.7.4. Construir la nueva GIC     
4.2.7.5. Forma normal de Chomsky     

4.2.8. Gramática independiente del contexto y su aplicación como reconocedor de la estructura sintáctica     
4.2.8.1. Derivación     
4.2.8.2. Árboles de derivación     
4.2.8.3. Ambigüedad     
4.2.8.4. Una gramática independiente del contexto no ambigua para expresiones regulares
4.2.8.5. Gramática de expresiones aritmética ambigua     
4.2.8.6. Árbol de análisis sintáctico     

4.2.8.7. Analizadores sintácticos     
4.2.8.7.1. Análisis sintáctico descendente gramática LL (I)     
4.2.8.7.1.1. Teorema gramática LL (I)     
4.2.8.7.1.2. Regla para eliminar recursividad izquierda     
4.2.8.7.1.3. Tabla LL y pila de evaluación     
4.2.8.7.1.4. Análisis sintáctico ascendente gramática LR     
4.2.8.7.1.5. Tabla LR y pila de evaluación

4.2.9. Gramáticas para lenguajes de programación    
4.2.10. Gramáticas para lenguajes naturales     
4.2.10.1. Forma normal de Chomsky (FNC)     
4.2.10.2. Forma normal de Greibach (FNG)     
4.2.11. Gramática de lenguajes regulares     
4.3. Ejercicios propuestos     

5. Autómatas con pila     

5.1. Autómatas con pila no determinísticos (APND)     
5.1.1. Arquitectura de un APND     
5.1.2. Definición formal de un APND     
5.1.3. Configuración instantánea de un APND     
5.1.4. Reconocimiento de un APND     
5.1.5. Transformación de un autómata que reconoce por estado de finalización a un autómata que reconoce por pila vacía     
5.1.6. Pasos de una GIC a un APND     
5.1.7. Conversión de una GIC a un APND que RxEF     
5.1.8. Conversión de una GIC a un APND que reconoce el LlC generado por G     
5.2. Ejemplos         
5.3. Ejercicios propuestos     

6. Máquinas de turing     

6.1. Definición formal de la máquina de Turing     
6.2. Función de transición     
6.3. Ejemplo del funcionamiento de una máquina de Turing     
6.4. Explicación del funcionamiento del ejemplo de máquina de Turing     
6.5. Descripción instantánea     

6.6. Movimientos de la máquina de Turing     
6.6.1. Izquierda     
6.6.2. Derecha     
6.6.3. Ejemplo     

6.7. Diagrama de transición para la máquina de Turing     
6.7.1. Ejemplos de diagrama de transición de una máquina de Turing     
6.8. Definición del lenguaje que evalúa una máquina de Turing     
6.8.1. Ejemplo No. 1     
6.8.2. Ejemplo No. 2     
6.8.3. Ejemplo No. 3     
6.8.4. Ejemplo No. 4         

Bibliografía