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

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

Temas

1. 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)
2. Relaciones entre autómatas formales, lenguajes y gramáticas
3. 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
4. Lenguajes Sensibles al Contexto (Tipo-1) y aplicaciones

Aprendizaje esperado (Learning Outcomes)

1. Para cada modelo formal en esta unidad:
   1. Explicar su definición comparando sus características con las otras en esta unidad
   2. Explicar ejemplos de entradas que son y no pueden ser aceptadas por el lenguaje/gramática.
   [Explicar]
2. Explicar las funciones Recursivas Primitivas y Generales (cero, sucesor, selección, recursión primitiva, composición y Mu), su importancia e implementaciones en Máquina de Turing [Explicar]
3. Explicar cómo se realiza la computación en el Cálculo Lambda (por ejemplo, conversión alfa y reducción beta) [Explicar]
4. Explicar el teorema de Rice y su importancia [Explicar]