Diferencia entre revisiones de «Finales Virtuales Tleng: Septiembre de 2020»
Sin resumen de edición |
Sin resumen de edición |
||
| Línea 4: | Línea 4: | ||
1) a) Dar un algoritmo que determine si un lenguaje regular dado es infinito. Dar la complejidad del algoritmo y justificar. | 1) a) Dar un algoritmo que determine si un lenguaje regular dado es infinito. Dar la complejidad del algoritmo y justificar. | ||
b) Sea GA1 una gramática de atributos bien definida. | b) Sea GA1 una gramática de atributos bien definida. | ||
Demostrar que es posible obtener una gramática de atributos GA2, equivalente a GA1, tal que GA2 no contiene atributos heredados. | Demostrar que es posible obtener una gramática de atributos GA2, equivalente a GA1, tal que GA2 no contiene atributos heredados. | ||
| Línea 23: | Línea 24: | ||
b) | b) | ||
Demostrar que, para todo k, toda gramática LR(k) | Demostrar que, para todo k, toda gramática LR(k) no es ambigua | ||
Revisión actual - 23:02 4 mar 2021
Los finales virtuales consistieron de uno o dos ejercicios escritos que le eran asignados a cada persona que rendia particularmente, abajo estan la lista de preguntas que se tomaron en las distintas fechas.
Septiembre
1) a) Dar un algoritmo que determine si un lenguaje regular dado es infinito. Dar la complejidad del algoritmo y justificar.
b) Sea GA1 una gramática de atributos bien definida. Demostrar que es posible obtener una gramática de atributos GA2, equivalente a GA1, tal que GA2 no contiene atributos heredados.
2) a) Considerar la siguiente forma normal de 3-Chomsky donde todas las producciones son de la forma
donde A, B, C, D son no terminales, a es terminal.
Dar un algoritmo que transforma una gramática libre de contexto sin producciones lambda a forma normal 3-Chomksy. Justificar la correctitud. Dar la complejidad computacional de este algoritmo.
b) Demostrar que, para todo k, toda gramática LR(k) no es ambigua
