Finales Virtuales Tleng: Marzo de 2022
De Cuba-Wiki
18 de febrero
Tomó Julio Jacobo. Se presentaron 3 personas.
Persona 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?)
- 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)
- 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
- Propiedades de indistinguibilidad (en particular la 4 y la 5)
- Condiciones para que un autómata de pila sea determinístico, y qué significan
- Jerarquía de Chomsky (ver persona anterior)
Persona 3
- Definición de autómatas de pila muy por arriba
- Pasaje de APD por EF a pila vacía (ver persona 1)
- Definición de expresiones regulares
- Pasaje de expresión regular a AFND-λ (preguntó pasaje de AFD a regex y persona 3 no sabía)
- 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.
- Decidir si las siguientes operaciones son cerradas o no respecto de los lenguajes libres de contexto y demostrarlo .
- Intersección
- Unión
- Complemento
- Concatenación
- Clausura de Kleene
- Sea
- Explicar por qué no es libre de contexto.
- Explicar por qué Pumping no sirve para demostrar el punto anterior (es decir, mostrar que el lenguaje cumple Pumping).
- Probar que no es libre de contexto. Venía con dos pistas:
- Pista: se puede usar que no es libre de contexto. Si además lo pueden demostrar suma puntos.
- Pista: se puede usar que, si notamos LIC a un lenguaje libre de contexto, vale que