PROGRAMA DE INGENIERÍA DE SISTEMAS

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 Alberto Amaya Tarazona

LECCIÓN 10. LENGUAJE ACEPTADO POR UN AF........................................................................ 48

CAPITULO 3: EXPRESIONES Y LENGUAJES REGULARES ................................................................. 50

LECCIÓN 11. LENGUAJES REGULARES Y EXPRESIONES REGULARES ......................................... 51

LECCIÓN 12. SIGNIFICADO DE LAS EXPRESIONES REGULARES .................................................. 51

LECCIÓN 13. AUTÓMATAS FINITOS Y EXPRESIONES REGULARES ............................................. 54

LECCIÓN 14. EQUIVALENCIA DE AFD Y AFND ............................................................................ 60

LECCIÓN 15. MINIMIZACIÓN DE AUTÓMATAS ......................................................................... 63

UNIDAD 2. LENGUAJES INDEPENDIENTES DEL CONTEXTO ............................................................... 69

CAPÍTULO 4 CONCEPTOS GENERALES ........................................................................................... 69

LECCIÓN 16. – GRAMÁTICAS REGULARES ................................................................................. 70

LECCIÓN 17. LENGUAJES LIBRES DE CONTEXTO Y SUS MÁQUINAS. ........................................ 76

LECCIÓN 18. ARBOLES DE DERIVACIÓN .................................................................................... 78

LECCIÓN 19. TRANSFORMACIÓN DE LAS GLC Y FORMAS NORMALES ...................................... 84

LECCIÓN 20. LIMITACIONES DE LOS LLC .................................................................................... 90

CAPITULO 5. AUTÓMATAS DE PILA ............................................................................................... 91

LECCIÓN 21. DEFINICIÓN DE AUTÓMATA CON PILA ................................................................. 92

LECCIÓN 22. FUNCIONAMIENTO DE LOS AUTÓMATAS DE PILA ............................................... 93

LECCIÓN 23. DISEÑO DE AUTÓMATAS DE PILA ......................................................................... 95

LECCIÓN 24. FUNCIONES QUE SE APLICAN SOBRE LOS STACKS. (PILAS). ................................ 98

LECCIÓN 25. COMBINACIÓN MODULAR DE AUTÓMATAS DE PILA ........................................ 100

CAPITULO 6: PROPIEDADES DE LOS LENGUAJES INDEPENDIENTES DE CONTEXTO.................... 101

LECCIÓN 26. LENGUAJE ACEPTADO POR UN AP ..................................................................... 101

7

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

LECCIÓN 27. RELACIÓN ENTRE LOS AUTÓMATAS

...