teoria de la computación
programa de la asignatura
Objetivo:
Comprender la importancia de los autómatas en el ámbito de la computación, para
aplicarlos en los diferentes casos, y poder así, obtener una mejor descripción de
un problema. Para llevar a cabo esta tarea, se requiere de un análisis del
problema, atendiendo a los requerimientos y objetivos del mismo, que en el área
de los autómatas, se aplican procedimientos particulares.
Contenido:
- Autómatas Finitos
Objetivo: Construir Autómatas Finitos (AF) para el reconocimiento y análisis de los Lenguajes Regulares.
1.1 Máquinas Abstractas.
1.2 Máquinas de Estados Finitos.
1.3 Autómatas Finitos Determinísticos (AFD).
1.4 Autómatas Finitos No Determinísticos (AFND).
1.5 Equivalencias de AFD y AFND.
1.6 Autómatas Finitos con salida. - Lenguajes Regulares (LR)
Objetivo: Explicar los fundamentos, diseño y organización de los lenguajes. 2.1 Alfabeto, cadena de caracteres.
2.2 Lenguajes y operaciones con Lenguajes.
2.3 Representación finita de Lenguajes.
2.4 Lenguajes Regulares.
2.5 Expresiones Regulares.
2.6 Análisis Léxico.
- Propiedades de los LR
Objetivo: Establecer Equivalencias de los LR, por medio de sus características, con las Expresiones Regulares, los Autómatas Finitos y las Gramáticas Regulares.
3.1 Equivalencia de expresiones Regulares y Autómatas Finitos.
3.2 Gramáticas Regulares.
3.3 Equivalencias de autómatas finitos y gramáticas regulares.
3.4 Limitaciones de los Lenguajes Regulares.
- Gramáticas y Lenguajes
Objetivo: Diferenciar los distintos lenguajes de acuerdo con la jerarquía de Chomsky y utilizar las técnicas elementales de transformación de gramáticas.
4.1 La jerarquía de Chomsky.
4.2 Lenguajes Libres de Contexto.
4.3 Gramáticas Libres y Sensitivas al Contexto.
4.4 Propiedades de las Gramáticas Libres de Contexto.
4.5 Forma Normal de Chomsky.
- Autómatas de Pila
Objetivo: Construir Autómatas de Pila para el reconocimiento y el análisis de los lenguajes libres de contexto.
5.1 Diseño de Autómatas de Pila.
5.2 Formalización de los Autómatas de Pila.
5.3 Relación entre Autómatas Finitos y Autómatas de Pila.
5.4 Relación entre Autómatas de Pila y Lenguajes Libres de Contexto.
5.5 Análisis sintáctico.
5.5.1 LL(1)
5.5.2 LR(0)
También puedes obtener el programa completo en pdf.
Criterios de evaluación
Se presentarán 3 exámenes, uno por cada parcial: el primero abarca las unidades 1 y 2, se presenta a principios de octubre; el segundo abarca las unidades 3 y 4, se presenta a mediados de noviembre; el tercero abarca la unidad 5 y se presenta a principios de diciembre.
Las tres calificaciones obtenidas en los exámenes representan el 80% y las tareas el 20% de cada calificación parcial. Las 3 calificaciones parciales se promediarán y si se obtienen 80 puntos o más, se exenta el examen ordinario; de lo contrario, el promedio obtenido representa el 60% de la calificación final y el examen ordinario el 40%.