Finales Virtuales Tleng: Septiembre de 2020

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

$A\rightarrow a$

$A\rightarrow BC$

$A\rightarrow BCD$

donde A, B, C, D son no terminales, a es terminal.

Dar un algoritmo que transforma una gramática libre de contexto $G=(V,N,P,S)$ 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