Edición de «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

<math> A \rightarrow a </math>

<math> A \rightarrow BC </math>

<math> A \rightarrow BCD </math>

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

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