Final del 27/12/18 (Teoría de Lenguajes)

Aclaración: el cuatrimestre fue más corto por lo que no se vieron todos los temas. Este final es el tomado a aquellos que cursaron con el programa reducido.

Ejercicio 1

• Demostrar el teorema de pasar de Expresión Regular a AFND-λ.
• Demostrar la vuelta del teorema.

Ejercicio 2

Dado un AFD, dar un algoritmo decidible que determine si acepta $\Sigma ^{*}$.

Ejercicio 3

Demostrar Pumping para GLC.

Ejercicio 4

Dar el algoritmo de parsing L(1). Dar un ejemplo pequeño (y árbol de derivación) y demostrar la complejidad.