Page 2 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

2

ÍNDICE

Contenido de Lenguajes formales, autómatas y compilados

 Entrega I. Conceptos Preliminares. 5
Introducción 6
Conceptos 7
Investigación: ¿Qué es el premio Turing? 8
Evolución Histórica de la Teoría de la Computación 9
Computabilidad 10
Investigación: Los Padres de la Computación 13
Complejidad Algorítmica 16
Máquinas Secuenciales y Autómatas Finitos 17
Teoría Algebraica de Lenguajes 19
Gramáticas y lenguajes formales 20
 Entrega II. Elementos Básicos De Los Lenguajes Formales
Y De Los Compiladores E Intérpretes. 21
Investigación: Noam Abraham Chomsky 24
Elementos Básicos De Los Lenguajes Formales Y 27
De Los Compiladores E Intérpretes. 28
Teoría De Conjuntos 29
Práctica 33
Cadenas 35
Lenguajes - Gramáticas Y Autómatas 38
Clasificación De Los Lenguajes Formales – Jerarquía De Chomsky 39
Tipos De Autómatas 41
Práctica 44
Compiladores E Intérpretes 45
Investigación: Compilador De C 48
Practica 51
Fases De La Compilación Vs Lenguajes Formales Vs Autómatas. 53
 Entrega III. Lenguajes Regulares Y Autómatas Finitos. 58
Práctica 63
 Entrega IV. Lenguajes Regulares Y No Regulares. 64
 Entrega V. Expresiones Regulares. 68
Práctica: Programa De Validación De Cédulas 69
Introducción A Autómatas De Pila, Gramática GLI Y Lenguajes GLI 70
 Entrega VI. Gramáticas Y Relaciones De Derivación Entre Cadenas. 73
 Entrega VII. Gramáticas Libres De Contexto. 78
Práctica 80
 Entrega VIII. Arboles De Derivación Y Ambigüedad 82
 Entrega IX. Gramática Independiente Del Contexto Que Requiere Un Ll 88
 Entrega X. Máquinas De Turing. 91
Construcción Modular De Máquinas De Turing. 95
Práctica 99
 Entrega XI. Máquinas De Turing II. 102
Práctica 104