Teoria de autonomas y lenguajes formales
Páginas: 292 (72809 palabras)
Publicado: 29 de marzo de 2011
Teor´ de Aut´matas y Lenguajes Formales ıa o
Alvaro E. Campos Pontificia Universidad Cat´lica de Chile o Escuela de Ingenier´ ıa Departamento de Ciencia de la Computaci´n o Marzo 1995
Contents
0 PROLOGO 0.1 ¿Qu´ es un Lenguaje? . . . . e 0.2 Sintaxis versus Sem´ntica . . a 0.3 Los Problemas a Estudiar . . 0.4 Aplicaci´n a Otros Problemas o 0.5 Clases de Lenguajes . . . . . 0.6 OtrosProblemas a Estudiar . 0.7 Problemas No Decidibles . . . 5 5 5 6 6 7 8 8 9 9 10 11 12 13 14 15 17 17 18 19 20 21 22 25 25 25 26 27 28 28 29 30 31 32 33
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
´ ´ 1 MATEMATICAS BASICAS 1.1 Conjuntos .. . . . . . . . . . . . . 1.1.1 Operaciones con Conjuntos 1.1.2 Conjuntos Infinitos . . . . . 1.2 Inducci´n Matem´tica . . . . . . . o a 1.2.1 Otras Bases . . . . . . . . . 1.2.2 Inducci´n Completa . . . . o 1.2.3 Definiciones Inductivas . . . 1.3 Grafos y Arboles . . . . . . . . . . 1.3.1 Grafos Dirigidos . . . . . . ´ 1.3.2 Arboles . . . . . . . . . . . 1.4 Relaciones Binarias . . . . . . . . .1.4.1 Propiedades . . . . . . . . . 1.4.2 Relaciones de Equivalencia 1.4.3 Clausuras . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . .. . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . .. . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
2 LENGUAJES FORMALES 2.1 S´ ımbolos y Alfabetos . . . . . . . . . .2.2 Palabras . . . . . . . . . . . . . . . . . 2.2.1 Longitud de una Palabra . . . o 2.2.2 Concatenaci´n . . . . . . . . . 2.2.3 Subpalabras, Prefijos y Sufijos 2.2.4 Reverso . . . . . . . . . . . . . 2.3 Lenguajes . . . . . . . . . . . . . . . . o 2.3.1 Concatenaci´n de Lenguajes . . 2.3.2 Clausuras . . . . . . . . . . . . 2.3.3 Representaci´n de Lenguajes . o 2.4 Aut´matas . . . . . . . . . . . . .. . o
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . . 1
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . .. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
2 ´ ´ 3...
Alvaro E. Campos Pontificia Universidad Cat´lica de Chile o Escuela de Ingenier´ ıa Departamento de Ciencia de la Computaci´n o Marzo 1995
Contents
0 PROLOGO 0.1 ¿Qu´ es un Lenguaje? . . . . e 0.2 Sintaxis versus Sem´ntica . . a 0.3 Los Problemas a Estudiar . . 0.4 Aplicaci´n a Otros Problemas o 0.5 Clases de Lenguajes . . . . . 0.6 OtrosProblemas a Estudiar . 0.7 Problemas No Decidibles . . . 5 5 5 6 6 7 8 8 9 9 10 11 12 13 14 15 17 17 18 19 20 21 22 25 25 25 26 27 28 28 29 30 31 32 33
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
´ ´ 1 MATEMATICAS BASICAS 1.1 Conjuntos .. . . . . . . . . . . . . 1.1.1 Operaciones con Conjuntos 1.1.2 Conjuntos Infinitos . . . . . 1.2 Inducci´n Matem´tica . . . . . . . o a 1.2.1 Otras Bases . . . . . . . . . 1.2.2 Inducci´n Completa . . . . o 1.2.3 Definiciones Inductivas . . . 1.3 Grafos y Arboles . . . . . . . . . . 1.3.1 Grafos Dirigidos . . . . . . ´ 1.3.2 Arboles . . . . . . . . . . . 1.4 Relaciones Binarias . . . . . . . . .1.4.1 Propiedades . . . . . . . . . 1.4.2 Relaciones de Equivalencia 1.4.3 Clausuras . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . .. . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . .. . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
2 LENGUAJES FORMALES 2.1 S´ ımbolos y Alfabetos . . . . . . . . . .2.2 Palabras . . . . . . . . . . . . . . . . . 2.2.1 Longitud de una Palabra . . . o 2.2.2 Concatenaci´n . . . . . . . . . 2.2.3 Subpalabras, Prefijos y Sufijos 2.2.4 Reverso . . . . . . . . . . . . . 2.3 Lenguajes . . . . . . . . . . . . . . . . o 2.3.1 Concatenaci´n de Lenguajes . . 2.3.2 Clausuras . . . . . . . . . . . . 2.3.3 Representaci´n de Lenguajes . o 2.4 Aut´matas . . . . . . . . . . . . .. . o
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . . 1
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . .. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
2 ´ ´ 3...
Leer documento completo
Regístrate para leer el documento completo.