5.20.4.3 Lenguajes Formales y Autómatas (16 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012,Kozen, 2006]

Temas

1. Autómatas formales:
   1. Estado Finito
   2. Pila
   3. Linealmente Acotado
   4. Máquina de Turing
2. Lenguajes formales, gramáticas y Jerarquía de Chomsky:
   1. Regulares (Tipo-3):
      1. Expresiones Regulares
   2. Libres de Contexto (Tipo-2)
   3. Sensibles al Contexto (Tipo-1)
   4. Recursivamente Enumerables (Tipo-0)
3. Decidabilidad, (in)computabilidad y parada
4. La tesis de Church-Turing
5. Reducibilidad y reducciones
6. Modelos equivalentes de computación algorítmica:
   1. Máquinas de Turing y Variaciones (por ejemplo, multicinta, no deterministas)
   2. Cálculo Lambda
   3. Funciones Mu-Recursivas

Aprendizaje esperado (Learning Outcomes)

1. Para cada autómata formal en esta unidad:
   1. Explicar su definición comparando sus características con los otros autómatas de esta unidad
   2. Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada
   3. Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata.
   [Explicar]
2. Explicar una Máquina de Turing universal y su operación [Explicar]
3. Presentar a una audiencia de compañeros de trabajo y gerentes la imposibilidad de proporcionarles un programa que verifique todos los otros programas, incluyendo algunos aparentemente simples, en busca de bucles infinitos incluyendo una explicación del problema de la parada, por qué no tiene solución algorítmica y su importancia para la computación algorítmica del mundo real [Explicar]
4. Explicar la Tesis de Church-Turing y su importancia para la computación algorítmica [Explicar]
5. Aplicar aritmetización y diagonalización para demostrar que el Problema de la Parada para Máquinas de Turing es Indecidible [Aplicar]
6. Dado un lenguaje indecidible conocido, aplicar una reducción por mapeo o historia computacional para demostrar que otro lenguaje es indecidible [Aplicar]