2.1.6 AL/Teoría y Computabilidad Avanzada de Autómatas

Temas:
Electivo

• Conjuntos y Lenguajes:
  1. Lenguajes Regulares.
  2. Revisión de autómatas finitos determinísticos (Deterministic Finite Automata DFAs)
  3. Autómata finito no determinístico (Nondeterministic Finite Automata NFAs)
  4. Equivalencia de DFAs y NFAs.
  5. Revisión de expresiones regulares; su equivalencia con autómatas finitos.
  6. Propiedades de cierre.
  7. Probando no-regularidad de lenguajes, a través del lema de bombeo (Pumping Lemma) o medios alternativos.
• Lenguajes libres de contexto:
  1. Autómatas de pila (Push-down automata (PDAs)
  2. Relación entre PDA y gramáticas libres de contexto.
  3. Propiedades de los lenguajes libres de contexto.
• Máquinas de Turing, o un modelo formal equivalente de computación universal.
• Máquinas de Turing no determinísticas.
• Jerarquía de Chomsky.
• La tesis de Church-Turing.
• Computabilidad.
• Teorema de Rice.
• Ejemplos de funciones no computables.
• Implicaciones de la no-computabilidad.

Objetivos de Aprendizaje (Learning Outcomes):
Elective:

1. Determina la ubicación de un lenguaje en la jerarquía de Chomsky (regular, libre de contexto, enumerable recursivamente) [Evaluar]
2. Convierte entre notaciones igualmente poderosas para un lenguaje, incluyendo entre estas AFDs, AFNDs, expresiones regulares, y entre AP y GLCs [Usar]
3. Explica la tesis de Church-Turing y su importancia [Familiarizarse]
4. Explica el teorema de Rice y su importancia [Familiarizarse]
5. Da ejemplos de funciones no computables [Familiarizarse]
6. Demuestra que un problema es no computable al reducir un problema clásico no computable en base a él [Usar]