Automatas
Páginas: 72 (17796 palabras)
Publicado: 25 de mayo de 2010
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 2. Sobre este documento 2.1. Versiones y lista de correcciones . . . . . . . . . . . . . . . . .. . . . . . . . . 3. Introducción 4. Conceptos básicos 4.1. Alfabetos . . . . . . . . . . . . . . . 4.2. Palabras . . . . . . . . . . . . . . . . 4.3. Lenguajes . . . . . . . . . . . . . . . 4.4. Producciones y Derivaciones . . . . . 4.5. Relaciones de equivalencia . . . . . . 4.6. Relación de equivalencia de lenguajes 5. Gramáticas generativas 5.1. Ejemplos . . . . . . . . . 5.2. Abreviación deBackus . . 5.3. Árbol de derivación . . . . 5.4. Jerarquia de Chomsky . . . 5.5. Equivalencia y ambigüedad 4 4 5 5 8 9 9 12 14 15 17 17 18 21 22 22 23 25 25 28 29 34 37 39 41 42 44 45 46 50 51
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . ..
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
6. Autómatas finitos 6.1. Autómatas finitos deterministas (AFD) . . . . . . . 6.2. Autómatas finitos no–deterministas (AFND) . . . . 6.3. Equivalencia entre AFD y AFND . . . . . . . . . . 6.4. Autómatas finitos no–deterministas con transiciones 6.5. Equivalencia entre AFND y AFND– . . .. . . . 6.6. Existencia de autómatas finitos mínimos . . . . . . 6.7. Ejemplos de uso del teorema de Myhill y Nerode . 6.8. Algoritmo de minimización . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . (AFND– . . . . . . . . . . . . . . . . . . . . . . . .
. . . ) . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . ..
. . . . . . . .
. . . . . . . .
. . . . . . . .
7. Expresiones regulares 7.1. Síntaxis y semántica . . . . . . . . . . . . . . . . . . . . . 7.2. Equivalencia entre autómatas finitos y expresiones regulares 7.3. Abreviaciones para el uso de expresiones regulares . . . . . 7.4. Símbolos y meta–símbolos . . . . . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
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 9.1. Propiedades de lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . . . . 9.2. Algoritmos de decisión de lenguages regulares . . . . . . . . . . . . . . . . . . . 9.3. Aplicaciones para lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . .
60 60 62 63
10. Lenguajes libres decontexto 63 10.1. Forma Normal de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 10.2. Forma Normal de Greibach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 10.3. Lema de bombeo para lenguajes libres de contexto . . . . . . . . . . . . . . . . 74 11. Autómatas finitos con pila (AFP) 11.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
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 2. Sobre este documento 2.1. Versiones y lista de correcciones . . . . . . . . . . . . . . . . .. . . . . . . . . 3. Introducción 4. Conceptos básicos 4.1. Alfabetos . . . . . . . . . . . . . . . 4.2. Palabras . . . . . . . . . . . . . . . . 4.3. Lenguajes . . . . . . . . . . . . . . . 4.4. Producciones y Derivaciones . . . . . 4.5. Relaciones de equivalencia . . . . . . 4.6. Relación de equivalencia de lenguajes 5. Gramáticas generativas 5.1. Ejemplos . . . . . . . . . 5.2. Abreviación deBackus . . 5.3. Árbol de derivación . . . . 5.4. Jerarquia de Chomsky . . . 5.5. Equivalencia y ambigüedad 4 4 5 5 8 9 9 12 14 15 17 17 18 21 22 22 23 25 25 28 29 34 37 39 41 42 44 45 46 50 51
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . ..
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
6. Autómatas finitos 6.1. Autómatas finitos deterministas (AFD) . . . . . . . 6.2. Autómatas finitos no–deterministas (AFND) . . . . 6.3. Equivalencia entre AFD y AFND . . . . . . . . . . 6.4. Autómatas finitos no–deterministas con transiciones 6.5. Equivalencia entre AFND y AFND– . . .. . . . 6.6. Existencia de autómatas finitos mínimos . . . . . . 6.7. Ejemplos de uso del teorema de Myhill y Nerode . 6.8. Algoritmo de minimización . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . (AFND– . . . . . . . . . . . . . . . . . . . . . . . .
. . . ) . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . ..
. . . . . . . .
. . . . . . . .
. . . . . . . .
7. Expresiones regulares 7.1. Síntaxis y semántica . . . . . . . . . . . . . . . . . . . . . 7.2. Equivalencia entre autómatas finitos y expresiones regulares 7.3. Abreviaciones para el uso de expresiones regulares . . . . . 7.4. Símbolos y meta–símbolos . . . . . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
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 9.1. Propiedades de lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . . . . 9.2. Algoritmos de decisión de lenguages regulares . . . . . . . . . . . . . . . . . . . 9.3. Aplicaciones para lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . .
60 60 62 63
10. Lenguajes libres decontexto 63 10.1. Forma Normal de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 10.2. Forma Normal de Greibach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 10.3. Lema de bombeo para lenguajes libres de contexto . . . . . . . . . . . . . . . . 74 11. Autómatas finitos con pila (AFP) 11.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
Leer documento completo
Regístrate para leer el documento completo.