adfjgfj
Páginas: 68 (16760 palabras)
Publicado: 30 de septiembre de 2013
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
2
Dr. Arno Formella
Índice
1. Curso
4
2. Sobre este documento
2.1. Versiones y lista de correcciones . . . . . . . . . .. . . . . . . . . . . . . . . .
4
5
3. Introducción
5
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
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
8
9
9
12
14
15
17
5. Gramáticas generativas
5.1. Ejemplos . . . . . . . . .
5.2. Abreviación de Backus . .
5.3. Árbol de derivación . . . .
5.4. Jerarquia de Chomsky . . .
5.5. Equivalencia y ambigüedad
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
18
21
22
22
23
. . . . . .
. . . . . .
. . . . . .
(AFND–
. . . . . .
. . . . . .
. . . . . .
. . . . . .
.
.
.
)
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
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 yNerode .
6.8. Algoritmo de minimización . . . . . . . . . . . . .
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...
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
2
Dr. Arno Formella
Índice
1. Curso
4
2. Sobre este documento
2.1. Versiones y lista de correcciones . . . . . . . . . .. . . . . . . . . . . . . . . .
4
5
3. Introducción
5
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
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
8
9
9
12
14
15
17
5. Gramáticas generativas
5.1. Ejemplos . . . . . . . . .
5.2. Abreviación de Backus . .
5.3. Árbol de derivación . . . .
5.4. Jerarquia de Chomsky . . .
5.5. Equivalencia y ambigüedad
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
18
21
22
22
23
. . . . . .
. . . . . .
. . . . . .
(AFND–
. . . . . .
. . . . . .
. . . . . .
. . . . . .
.
.
.
)
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
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 yNerode .
6.8. Algoritmo de minimización . . . . . . . . . . . . .
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...
Leer documento completo
Regístrate para leer el documento completo.