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

1. Sea $L=\{a^{i}b^{j}c^{k}d^{l}:i=0\lor j=k=l\}$
   1. Explicar por qué no es libre de contexto.
   2. Explicar por qué Pumping no sirve para demostrar el punto anterior (es decir, mostrar que el lenguaje cumple Pumping).

1. Probar que $\{ww:w\in \{a,b\}*\}$ no es libre de contexto. Venía con dos pistas:
   1. Pista: se puede usar que $\{a^{n}b^{m}a^{n}b^{m}:m,n\geq 0\}$ no es libre de contexto. Si además lo pueden demostrar suma puntos.
   2. Pista: se puede usar que, si notamos LIC a un lenguaje libre de contexto, vale que $LIC\cap {\text{Regular}}=LIC$