AL7. Teoría de Autómatas.

Tópicos

• Autómatas finitos deterministas (DFA).
• Autómatas finitos no deterministas (NFA).
• Equivalencias entre los DFA y NFA.
• Expresiones regulares.
• El teorema del bombeo (pumping) para expresiones regulares.
• Autómatas de pila (PDA).
• Relación entre los PDA y las gramáticas libres del contexto.
• Propiedades de las gramáticas libres del contexto.
• Máquinas de Turing.
• Máquinas de Turing no determinísticas.
• Conjuntos y lenguajes.
• La jerarquía de Chomsky.
• La tesis de Church-Turing.

Objetivos

• 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).
• Probar que un lenguaje se encuentra en una clase específica y que este no se encuentra en la siguiente clase inferior.
• Conversiones entre notaciones potentes equivalentes para un lenguaje, incluyendo conversiones entre DFAs, NFAs, y expresiones regulares, y entre PDA y CFG.
• Explicar al menos un algoritmo de parsing top-down (de análisis de arriba hacia abajo) o bottom-up (de análisis abajo hacia arriba).
• Explicar la tesis de Church-Turing y su importancia.