Diferencia entre revisiones de «Final del 27/12/18 (Teoría de Lenguajes)»

De Cuba-Wiki
(Página creada con «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…»)
 
Sin resumen de edición
 
Línea 12: Línea 12:


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

Revisión actual - 18:03 31 ene 2019

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 .

Ejercicio 3

Demostrar Pumping para GLC.

Ejercicio 4

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