Secciones

Sub-secciones

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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%.