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[editar]
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
