Nota: El proyecto se
deberá entregar funcionando a más tardar el
miércoles 7 de diciembre a las 4pm. A esa hora los espero en mi
oficina.
Los cinco proyectos que se realizarán son sobre
gramáticas libres del contexto y son los siguientes:
Eliminación de símbolos que no generan cadenas de
terminales (123-125).
Eliminación de símbolos que no aparecen en ninguna
derivación (125-126).
Eliminación de símbolos anulables (126-128).
Eliminación de producciones unitarias (128-130).
Forma normal de Chomsky (130-132).
Los cinco programas se deberán entregar en fuente y ejecutable
que compilen sin problemas en Linux (gcc, g++ o gcj). Pasen a mi
oficina para que les de cuentas de mi máquina (SSH
148.206.67.155) y puedan probar allí sus programas.
gcc
programa.c -o programa g++ programa.cpp -o programa gcj --main=programa -Wall
programa.java -o programa
Cada programa
leerá una gramática libre de contexto de su entrada
estándar y escribirá una gramática libre de
contexto en su salida estándar. Ningún programa
deberá leer ni escribir ningún dato adicional. Una
gramática quedará definida de la siguiente forma: Los
caracteres del alfabeto serán siempre las letras
minúsculas de la a
a la z (sin incluir las
letras con acentos). La cadena vacía será representada
por la @. Los
símbolos no terminales constarán de una letra
mayúscula de la A
a la Z y posiblemente una
cadena de dígitos. Una producción estará
representada por un no terminal seguido de un guión - seguido de una cadena formada
por caracteres del alfabeto, no terminales y cadenas vacías. La
primera producción que aparezca define el símbolo
inicial. Varias producciones del mismo no terminal podrán
aparecer separadas por barras verticales |. Las producciones
podrán estar distribuidas en varios renglones
(independientemente de que sean del mismo no terminal o no) y
podrán aparecer repetidas.
Como ejemplo, la gramática S -> bA | aB, A -> bAA | aS |
a, B -> aBB | bS | b se podría representar en la entrada de
cualquiera de las tres formas:
S-bA|aB
A-bAA|aS|a
B-aBB|bS|b
S-bA
A-aS
S-aB|bA
B-bS|b|b
A-bAA|a
B-aBB
S-b@A|aB@
B-b
A-b@A@A|aS|a
B-aBB|bs
Sin embargo, una gramática de salida sólo se podrá
representar de una forma: No debe contener @ innecesarias, los no
terminales sólo deben aparecer una vez al lado izquierdo de las
producciones y, salvo el símbolo inicial que debe aparecer
primero, deben aparecer en orden alfabético (@ es menor que cualquier letra
minúscula que es menor que cualquier letra mayúscula).
Finalmente, todas las producciones del mismo no terminal también
deben aparecer en orden alfabético sin repeticiones. Por lo
tanto, las siguientes son posibles representaciones de
gramáticas a la salida:
S-aB|bA
A-a|aS|bAA
B-aBB|b|bS
S-aA
A-@|aA
S-C1B|C2A
A-a|C1S|C2AA
B-b|C1BB|C2S
C1-a
C2-b
Para cualquier otra duda acerca del formato de entrada y salida,
pregúntenme.