4.3.7 AL/Teoría de Autómatas.

Tópicos

• Autómatas finitos determinísticos (DFAs).
• Autómatas finitos no determinísticos (NFAs).
• Equivalencias entre los DFAs y NFAs.
• Expresiones regulares.
• El teorema del bombeo (pumping) para expresiones regulares.
• Autómatas de pila (PDAs).
• Relación entre los PDAs 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 así como entre PDAs y CFGs.
• 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).
• Explicar la tesis de Church-Turing y su importancia.