4.26.4.3 AL/Teoría de Autómatas. (20 horas) [Nivel Bloom 3]

Referencias Bibliográficas: [,]

Tópicos

  1. Autómatas finitos determinísticos (DFAs).
  2. Autómatas finitos no determinísticos (NFAs).
  3. Equivalencias entre los DFAs y NFAs.
  4. Expresiones regulares.
  5. El teorema del bombeo (pumping) para expresiones regulares.
  6. Autómatas de pila (PDAs).
  7. Relación entre los PDAs y las gramáticas libres del contexto.
  8. Propiedades de las gramáticas libres del contexto.
  9. Máquinas de Turing.
  10. Máquinas de Turing no determinísticas.
  11. Conjuntos y lenguajes.
  12. La jerarquía de Chomsky.
  13. La tesis de Church-Turing.

Objetivos

  1. Determinar la localización de un lenguaje en la jerarquía de Chomsky (conjuntos regulares, libres del contexto, sensibles al contexto y lenguajes enumerables recursivos).
  2. Probar que un lenguaje se encuentra en una clase específica y que este no se encuentra en la siguiente clase inferior.
  3. Conversiones entre notaciones potentes equivalentes para un lenguaje, incluyendo conversiones entre DFAs, NFAs y expresiones regulares así como entre PDAs y CFGs.
  4. Explicar al menos un algoritmo de de análisis de arriba hacia abajo (parsing top-down) o de análisis de abajo hacia arriba (bottom-up).
  5. Explicar la tesis de Church-Turing y su importancia.

Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, Universidad Católica San Pablo, Arequipa-Peru
basado en el modelo de la Computing Curricula de IEEE-CS/ACM