4.15.5.1 Autómatas y Lenguajes (20 horas) [Habilidades a,1]

Referencias Bibliográficas: [Sipser, 2012,Hopcroft and Ullman, 2008,Brookshear, 1993] Temas

1. 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.
2. Gramáticas libres de contexto.
3. 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.

Objetivos de Aprendizaje

1. Determina la ubicación de un lenguaje en la jerarquía de Chomsky (regular, libre de contexto, enumerable recursivamente) [Assessment]
2. Convierte entre notaciones igualmente poderosas para un lenguaje, incluyendo entre estas AFDs, AFNDs, expresiones regulares, y entre AP y GLCs [Assessment]
3. Discute el concepto de máquina de estado finito [Assessment]
4. Diseñe una máquina de estado finito determinista para aceptar un determinado lenguaje [Assessment]
5. Genere una expresión regular para representar un lenguaje específico [Assessment]
6. Diseñe una gramática libre de contexto para representar un lenguaje especificado [Assessment]