Teoria de automatas

Teoría de Autómatas y Lenguajes Formales
Version 2
Dr. Arno Formella
Universidad de Vigo
Departamento de Informática
Área de Lenguajes y Sistemas Informáticos
E-32004 Ourense
http://www.ei.uvigo.es/˜formella
formella@ei.uvigo.es
11 de junio de 2006
Dr. Arno Formella 2
Índice
1. Curso 4
2. Sobre este documento 4
2.1. Versiones y lista de correcciones . . . . . . . . . . . . . . . .. . . . . . . . . . 5
3. Introducción 5
4. Conceptos básicos 8
4.1. Alfabetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2. Palabras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4. Producciones y Derivaciones . . . . . . . .. . . . . . . . . . . . . . . . . . . . 14
4.5. Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.6. Relación de equivalencia de lenguajes . . . . . . . . . . . . . . . . . . . . . . . 17
5. Gramáticas generativas 17
5.1. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2. Abreviación de Backus . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 21
5.3. Árbol de derivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.4. Jerarquia de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.5. Equivalencia y ambigüedad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6. Autómatas finitos 25
6.1. Autómatas finitos deterministas (AFD) .. . . . . . . . . . . . . . . . . . . . . . 25
6.2. Autómatas finitos no–deterministas (AFND) . . . . . . . . . . . . . . . . . . . . 28
6.3. Equivalencia entre AFD y AFND . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.4. Autómatas finitos no–deterministas con transiciones  (AFND–) . . . . . . . . . 34
6.5. Equivalencia entre AFND y AFND– . . . . . . . . . . . . . . . . . . . . .. . 37
6.6. Existencia de autómatas finitos mínimos . . . . . . . . . . . . . . . . . . . . . . 39
6.7. Ejemplos de uso del teorema de Myhill y Nerode . . . . . . . . . . . . . . . . . 41
6.8. Algoritmo de minimización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7. Expresiones regulares 44
7.1. Síntaxis y semántica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 45
7.2. Equivalencia entre autómatas finitos y expresiones regulares . . . . . . . . . . . 46
7.3. Abreviaciones para el uso de expresiones regulares . . . . . . . . . . . . . . . . 50
7.4. Símbolos y meta–símbolos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
8. Lenguajes regulares 51
8.1. Equivalencia entre gramáticas lineales por la derecha y autómatas finitos . . . . .51
8.2. Equivalencia entre gramáticas lineales por la derecha y lineales por la izquierda . 53
Dr. Arno Formella 3
8.3. Lema de bombeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
9. Propiedades, algoritmos de decisión,
y aplicaciones para lenguajes regulares 60
9.1. Propiedades de lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . . . . 60
9.2.Algoritmos de decisión de lenguages regulares . . . . . . . . . . . . . . . . . . . 62
9.3. Aplicaciones para lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . . 63
10. Lenguajes libres de contexto 63
10.1. Forma Normal de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
10.2. Forma Normal de Greibach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7210.3. Lema de bombeo para lenguajes libres de contexto . . . . . . . . . . . . . . . . 74
11. Autómatas finitos con pila (AFP) 76
11.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
11.2. Autómatas finitos con pila no–deterministas (AFPND) . . . . . . . . . . . . . . 77
11.3. Equivalencia entre AFPNDs aceptando con pila vacía y aceptando en estado final...