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

Referencias Bibliográficas: [Sipser, 2012,Hopcroft et al., 2013]

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. Formas Normales: Chomsky y Greibach
4. Demostraciones del Lema de Bombeo:
   1. Demostración de la limitación de Estado Finito/Lenguaje Regular
   2. Limitación de Autómatas de Pila/Lenguaje Libre de Contexto
5. Relaciones entre autómatas formales, lenguajes y gramáticas

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. Dado un problema, desarrollar un autómata apropiado que aborde el problema [Crear]
3. Convertir entre notaciones equivalentemente poderosas para un lenguaje, incluyendo entre DFAs, NFAs y expresiones regulares, y entre PDAs y CFGs [Aplicar]
4. Aplicar lemas de bombeo, o medios alternativos, para demostrar las limitaciones de los autómatas de Estado Finito y Pila [Aplicar]
5. Construir GLCs para descripciones de lenguajes formales [Evaluar]