Examen Final [solución]

      Duración: dos horas. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva tres de las preguntas. ¡No haga más de lo que se le pide!

1.a) [11 pts] Haga el diagrama del autómata L11 que reconozca hileras en el alfabeto Σ = {0,1} en las que siempre que aparece al principio una hilera de 3 símbolo formada por un cero (0) y 2 unos (1), y que al final de la hilera no es un par de unos (11). Por ejemplo la hilera "1010001100101" está en L11 pues comienza con "101" y termina con "01", que no es "11".

1.b) [0 pts] Haga un autómata que reconozca los prefijos válidos para una hilera que está en el lenguaje L.

1.c) [11 pts] Encuentre el autómata noL11 que reconoce el lenguaje complementario de L11, esto es, el autómata que cumple estas condiciones: (Σ^* = L11 U noL11) & (Σ^* - L11 = noL11) & (L11 ∩ noL11 =Θ)

1.d) [11 pts] Minimice el autómata noL11. Muestre el diagrama final del autómata minimizado.

1.e) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

S => X Y a Z b
X => Y b X a | Z a
Y => ε
Z => ε

2.a) [11 pts] Haga la tabla LL(1) para G.

2.b) [11 pts] Haga la tabla LR(1) para G.

2.c) [5 pts] Haga el análisis sintáctico ascendente de la hilera "baab" haciendo uso de la tabla obtenida en el punto anterior.

2.d) [6 pts] Si esta gramática fuera usada para obtener un analizador sintáctico con Yacc/Bison, ¿cuáles serían la tabla que se obtendría?

  3) [33 pts] Usted ha sido contratado por la CIA para examinar los documentos que fueron incautados a la red internacional de terrorismo Al-Qaeda. Por eso, usted tiene más de 100,000 archivos repartidos en varios directorios, en los que hay documentación sobre los planes de destrucción masiva de esta organización terrorista.

      Para examinar los documentos se necesita extraer información basada en palabras clave. La manera de hacerlo es con el programa "BQ-plb" que encuentre aquellos archivos que contienen las palabras buscadas.

      Su programa debe recibir una lista de palabras y encontrar todos los documentos que las contienen, tanto en el nombre del archivo como en su contenido. Con un '+' se pueden separar varios grupos de palabras, y con el '-' se puede indicar que deben aparecer 2 palabras, pero una seguida después de la otra. Esta es una posible ejecución de su programa:

D:\CIA\Al-Qaeda> BQ-plb bomb air + bus - secuestro + terremoto + quake

book 2\Secuestro y asesinato en vehículos motorizados.html
JLkmx\No más -- Un grito de esperanza.txt
Junio-18\Air strike repercutions.pdf
Junio-18\Un tsunami contra París.doc

      El operador '+' tiene el efecto de un operador de "OR" de disjunción, mientras que el espacio en blanco ' ' sirve para especificar que ambas palabras deben aparecer en el documento. Por eso la expresión "bomb air" sirve para localiza aquellos documentos que contengan ambas palabras ("bomb" y "air"). Un efecto similar tiene el operador '-', pero en este caso se requiere que una palabra aparezca antes en documento que la otra, como ocurre con la hilera "bus - secuestro", en donde el programa encontrará los documentos que contengan ambas palabras pero en donde "bus" aparezca en el documento antes que "secuestro".

3.a) [7 pts] Escriba una gramática que sirva para las hileras válidas de búsqueda del programa "BQ-plb". Defina correctamente la precedencia de los operadores.

3.b) [16 pts] Suponga que usted ya cuenta con la función
  bool Busque( const char * F, const char * plb, unsigned & pr, unsigned & ul );
que pone en "pr" posición en donde aparece por primera vez la palabra "plb" en el archivo "F" y en "ul" adonde aparece por última vez. Como la numeración comienza en "1", si ocurre que "pr == ul == 0" eso quiere decir que en el archivo"F" no contiene la hilera "* plb"; éste es el único caso en que "Busque()" retorna "false". Si lo desea, busque en el directorio actual y en todos sus subdirectorios, o si no suponga que existe un archivos llamado "BQ-plb.dir" que contiene el nombre de cada uno de los archivos en los que hay que aplicar "Busque()".

      Use la función "Busque()" para incorporarle a su gramática las acciones que se requieran para que "BQ-plb" calcule sus resultados.

3.c) [10 pts] Use Lex para implementar el analizador léxico para "BQ-plb".

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2004
Derechos de autor reservados © 2004