Finales Virtuales Tleng: Marzo de 2022

18 de febrero

Tomó Julio Jacobo. Se presentaron 3 personas.

Persona 1

1. Pasaje de APD por estado final a APD por pila vacía (qué puede fallar si no agregás el nuevo símbolo inicial a la pila?)
2. Demostración de por qué el AFD de estados mínimos es mínimo (daba por asumido el lema y lo escribía si hacía falta)
3. Contar qué tipos de gramáticas vimos de la jerarquía de Chomsky y qué autómatas las reconocen (tipos 0, 1, 2 y 3)

Persona 2

1. Propiedades de indistinguibilidad (en particular la 4 y la 5)
2. Condiciones para que un autómata de pila sea determinístico, y qué significan
3. Jerarquía de Chomsky (ver persona anterior)

Persona 3

1. Definición de autómatas de pila muy por arriba
2. Pasaje de APD por EF a pila vacía (ver persona 1)
3. Definición de expresiones regulares
4. Pasaje de expresión regular a AFND-λ (preguntó pasaje de AFD a regex y persona 3 no sabía)
5. Propiedades de los lenguajes libres de contexto respecto de la unión, intersección y complemento

4 de marzo

Tomó Julio Jacobo escrito, eran 3 ejercicios.

1. Decidir si las siguientes operaciones son cerradas o no respecto de los lenguajes libres de contexto y demostrarlo .
   1. Intersección
   2. Unión
   3. Complemento
   4. Concatenación
   5. Clausura de Kleene