Contenido (Unidad /
Competencia / Actividad / Material de Aprendizaje) |
1. Introducción
1.1. Conceptos Básicos
1.1.1. Autómatas
Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pag 6 (260176 bytes)
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito#Definici.C3.B3n_formal
1.1.2. Nociones Matemáticas
Juan Manuel, Cueva Lovelle. 2001. Lenguajes, Gramáticas y Autómatas. Segunda Edición. Universidad de Oviedo. Pag. 3
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. Pags 3-11
Introducción (76179 bytes)
Conceptos Básicos (112433 bytes)
1.2. Métodos de Validación
1.2.1. Inducción Matemática
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. Pags 15-16
Carlos Chinea. Sobre la Inducción Matemática. Junio de 2003 (137191 bytes)
Problemas de Inducción Matemática (117735 bytes)
http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica
1.2.2. Técnica de lo Absurdo
Método de lo Absurdo (65100 bytes)
http://es.wikipedia.org/wiki/Reducci%C3%B3n_al_absurdo
|
2. Lenguajes Regulares
2.1. Autómatas Finitos
2.1.1. Determinísticos
Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 59-66
Unidad II. Lenguajes Regulares (176309 bytes)
Autómatas finitos determinísticos (99840 bytes)
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito#Definici.C3.B3n_formal
2.1.2. No Determinísticos
Autómatas finitos no determinísticos (171008 bytes)
Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 66-70
Unidad II.Lenguajes Regulares. Autómatas No Determinísticos ( bytes)
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito#Definici.C3.B3n_formal
2.2. Expresiones regulares
2.2.1. Operaciones
Juan Manuel Cueva Lovelle. 2001. Lenguajes, Gramáticas y Autómatas. 2a Edición. Universidad de Oviedo. 29-33
Ramón Brena. 2003. Autómatas y Lenguajes, Un enfoque de Diseño. Tec. de Monterrey. 81-83
Expresiones Regulares (161964 bytes)
Equivalencia de Expresiones Regulares (293375 bytes)
2.2.2. Lenguajes No Regulares
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 100-104
Lenguajes Regulares (160798 bytes)
|
3. Lenguajes Libres de Contexto
3.1. Gramáticas
3.1.1. Árboles de derivación
Cómo dibujar un árbol sintáctico (115712 bytes)
Gráficos y Árboles (51200 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 95-97,111-122
Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 7-10
3.1.2. Formas Normales
Forma Normal de Greibach (90112 bytes)
Forma Normal de Chomsky (40960 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 132-136
3.1.3. Recursividad
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 123-124
Recursividad (263690 bytes)
3.1.4. Ambigüedad
Árboles y gramáticas (50688 bytes)
Ambigüedad (38912 bytes)
Equivalencia y Ambigüedad (44544 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 124-125
3.2. Autómatas Push-Down
3.2.1. Lenguajes Libres de Contexto
Autómatas de Pila y Lenguajes Libres de Contexto (152576 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 145-149
Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 49-58
Lenguajes Libres de Contexto (310371 bytes)
3.2.2. Lenguajes no regulares
Lenguajes Libres de Contexto (36352 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 136-139
Lema de Bombeo (82145 bytes)
|
4. Máquinas de Turing
4.1. Diseño
4.1.1. Definición de Máquina de Turing
Máquina de Turing (61440 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 169-174
4.1.2. Construcción modular
Construccion Modular (35328 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 178-180
4.1.3. Lenguajes Aceptados
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pag 192-194
Lenguajes Aceptados (160418 bytes)
4.2. Lenguajes
4.2.1. Variantes de una máquina de Turing
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pag 184
Variaciones de las MT (53789 bytes)
4.2.2. Problemas de Hilbert
Problemas de Hilbert (904408 bytes)
|
5. Decibilidad
5.1. Lenguajes Decidibles
5.1.1. Definición
Teoria de la Computacion (59392 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 139-140,181-182
5.1.2. El problema de Halting
Problema de Correspondencia de Post (46592 bytes)
Problema de Decisión (29184 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 191-192
5.2. Teorías Lógicas
5.2.1. Decidibilidad
Decibilidad (25600 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 184-186
5.2.2. Lenguajes
Teoría de la Computación (39424 bytes)
http://delta.cs.cinvestav.mx/~gmorales/complex/node78.html
|
6. Reducibilidad
6.1. Teoría de Lenguajes
6.1.1. Problemas insolubles para la teoría de lenguajes
Problema de la Parada (44032 bytes)
6.1.2. Un problema simple insoluble
Ejemplos de Problemas Insolubles (28672 bytes)
6.2. Funciones Computables
6.2.1. Computabilidad
Funciones Computables (71680 bytes)
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 179-181
6.2.2. Reducibilidad de Turing
Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 47-53
Reducibilidad e Indecibilidad (164746 bytes)
|