# Pregunta 3 en examen II26 - 19 de diciembre de 2008 Esta solucion se basa en [Louden 2004 pag. 154-155]. Aqui =>* denota una derivacion en cero o mas pasos, lambda denota la cadena vacia, y alfa, beta, gamma y delta denotan formas sentenciales formadas por cero o mas terminales y no terminales. Reservamos y alfa para lo que propone el enunciado del examen y adaptamos la notacion. Una gramatica es LL(1) si la tabla de analisis sintactico LL(1) asociada tiene como maximo una produccion en cada entrada de la tabla. Esa tabla se construye de acuerdo con las reglas siguientes (pag. 154): 1. Si -> beta es una produccion y existe una derivacion beta =>* b gamma donde b es un terminal, entonces se agrega -> beta a la entrada de tabla M[,b]. 2. Si -> beta es una produccion y existen derivaciones beta =>* lambda $ =>* delta b gamma donde es el no terminal inicial y b es un terminal (o $), entonces se agrega -> beta a la entrada de tabla M[,b]. Es bastante obvio que, con la transformacion del enunciado del examen, esos tres tipos de derivaciones existen con la gramatica resultante si y solo si existian con la gramatica original, con la diferencia de que si en beta aparecia el no terminal ahora aparecera alfa, y si en algun paso se derivaba algo que contenia y mas tarde se sustituia por alfa, ahora obtendremos directamente alfa en la misma posicion. Por tanto, la gramatica transformada tendra una tabla de analisis que coincidira con la de la gramatica original excepto por la desaparicion de la fila de y la sustitucion de por alfa en cualquier parte derecha beta. Por ello no habra mas de una produccion en ninguna entrada si no la habia antes, y si la gramatica original era LL(1) la gramatica transformada seguira siendo LL(1). Dicho de otro modo, la regla 1 equivale a introducir -> beta en M[,b] si b esta en PRIMEROS(beta), y la regla 2 equivale a hacerlo si beta es ANULABLE y b esta en SIGUIENTES(), y el razonamiento anterior equivale a decir que el calculo de ANULABLES, PRIMEROS y SIGUIENTES con la gramatica transformada no produce entradas con mas producciones que con la gramatica original, si no habia conflictos con la gramatica original no los habra con la gramatica transformada.