4.15.2.3 Teoría y Computabilidad Avanzada de Autómatas (20 horas) [Habilidades j]

Referencias Bibliográficas: [Hopcroft and Ullman, 1993,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. 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]