PROGRAMA DE INGENIERÍA DE SISTEMAS
Enviado por fafdgfgui • 6 de Marzo de 2014 • 2.559 Palabras (11 Páginas) • 385 Visitas
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA
PROGRAMA DE INGENIERÍA DE SISTEMAS
301405 – AUTÓMATAS Y LENGUAJES FORMALES
AUTOR:
CARLOS ALBERTO AMAYA TARAZONA (Director Nacional)
http://www.camayat.com
Duitama (ZCBOY)
Versión 3 – 2014.
CONTENIDO
Primera Unidad Capítulos Lecciones
I. LENGUAJES
REGULARES
1. Conceptos Básicos
1. Introducción e Historia.
2. Alfabetos, Cadenas y Lenguajes
3. Autómatas y Lenguajes.
4. Lenguajes Regulares
5. Autómata
2. Autómatas Finitos
6. Definición Formal de Autómatas Finitos
7. Autómatas Finitos Determinísticos (AFD)
8. Autómatas Finitos no Determinísticos (AFND)
9. Autómatas Finitos con Transacciones
10. Lenguaje Aceptado por Autómata Finito
3. Expresiones Regulares
11.Lenguajes Regulares y Expresiones Regulares
12. Significado de las Expresiones Regulares
13. Autómatas Finitos y Expresiones Regulares
14 Equivalencia de Autómatas Finitos
Determinísticos y Autómatas Finitos no
Determinísticos
15 Minimización de Autómatas
Segunda Unidad
Capítulos
Lecciones
II. LENGUAJES
INDEPENDIENTES DEL
CONTEXTO
4. Conceptos Generales
16. Gramáticas Regulares
17. Lenguajes libres de contexto y sus máquinas
18. Arboles de derivación
19. Transformación de las GLC y Formas Normales
20.Limitacioes de los LLC
5. Autómatas a Pila
21. Definición de Autómata con Pila
22. Funcionamiento de Autómata con Pila
23. Diseño de Autómata con Pila.
24. Funciones que se aplican sobre los stacks (Pilas)
25. Combinación modular de los autómatas con Pila
6. Propiedades de Lenguajes
Independientes de Contexto
26. Lenguaje aceptado por un AP
27. Relación entre los AP y los LLC
28. Propiedades de clausura de los Lenguajes
Libres de Contexto
29. Algoritmos de decisión para los LLC
30.Problemas Indecibles para Lenguajes Libres de
Contexto
Tercera Unidad
Capítulos
III. LENGUAJES
ESTRUCTURADOS POR
FRASES
7. Máquinas de Turing.
31. Formalización de las MT
32. Funcionamiento de la Máquina de Turing.
33. Diferencias entre un Computador y una
Máquina de Turing
34. La Máquina Universal de Turing
4
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA
MODULO CURSO: 301405 – AUTÓMATAS Y LENGUAJES FORMALES. Ing. (Msc). Carlos Alberto Amaya Tarazona
35. Lenguajes aceptados por la MT
8. Máquina de Turing y Computación
36. Tesis de Church/Turing
37.Variantes de Una Máquina de Turing
38. Problemas de Hilbert
39. Problemas Insolubles para la Teoría de Lenguajes
40. Lenguajes Decidibles
9. Funciones Recursivas
41. Problemas de Halting
42. Decibilidad de Teorías Lógicas
43. Reducibilidad de Turing
44. Algoritmo de Trellis
45. Algoritmo de Viteri
5
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA
MODULO CURSO: 301405 – AUTÓMATAS Y LENGUAJES FORMALES. Ing. (Msc). Carlos Alberto Amaya Tarazona
Tabla de contenido
LISTA DE FIGURAS................................................................................................................................ 8
LISTA DE TABLAS................................................................................................................................ 10
INTRODUCCIÓN ................................................................................................................................. 11
ANEXO 1: LISTADO DE SÍMBOLOS USADOS....................................................................................... 14
ANEXO 2: PRESABERES: TEORÍA DE CONJUNTOS .............................................................................. 16
I. GENERALIDADES: ............................................................................................................ 16
I.I OPERACIONES CON CONJUNTOS: ......................................................................................... 17
I.II EQUIVALENCIAS DE CONJUNTOS: ........................................................................................ 19
I.III RELACIONES:........................................................................................................................ 20
I.IV FUNCIONES: ........................................................................................................................ 24
PRIMERA UNIDAD: LENGUAJES REGULARES ..................................................................................... 25
CAPITULO 1: CONCEPTOS BÁSICOS ............................................................................................... 25
LECCIÓN 1: INTRODUCCIÓN E HISTORIA: .................................................................................. 26
LECCIÓN 2. - ALFABETOS, CADENAS Y LENGUAJES ................................................................. 28
LECCIÓN 3. AUTÓMATAS Y LENGUAJES ................................................................................... 31
LECCIÓN 4. LENGUAJES REGULARES ........................................................................................ 33
LECCIÓN 5. AUTÓMATA ............................................................................................................ 36
CAPITULO 2. AUTÓMATAS FINITOS ............................................................................................... 39
LECCIÓN 6. DEFINICIÓN FORMAL DE AUTÓMATAS FINITOS .................................................... 39
LECCIÓN 7. AUTÓMATAS FINITOS DETERMINÍSTICOS (AFD) .................................................... 42
LECCIÓN 8. AUTÓMATAS FINITOS NO DETERMINÍSTICOS (AFND)............................................ 45
LECCIÓN 9. AUTÓMATA FINITO CON TRANSICIONES ........................................................... 47
6
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA
MODULO CURSO: 301405 – AUTÓMATAS Y LENGUAJES FORMALES. Ing. (Msc). Carlos
...