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.