CI-1322 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2009

$[\/]$

CI-1322 Autómatas y compiladores

Examen #1 [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 y escoja entre la Versión [A] y la Versión [B] según más le convenga. ¡No haga más de lo que se le pide!

1) [33 pts] Versión [A].

En el lenguaje de las colinas se usan los caracteres Σ = { '\' '=' '/' } para dibujar una hilera que tiene una concavidad. Si se comienza a subir con al menos 2 '/' luego se puede encontrar varias '=' o más subidas '/', pero a fin de cuentas deben haber al menos 2 bajadas '\', aunque puede que las 2 letras de subida o bajada estén separadas por varios '=', como en "

=/===///===\=\= 
...

". En otras palabras, si hay 2 subidas también deben haber 2 bajadas, aunque en el medio puede que haya varios '='.

           / === \
          /        = \
         /             =
   = = =
= /

1.a) [0 pts] Escriba una expresión regular "Colina" que sirva para determinar si una hilera tiene colinas.

1.b) [11 pts] Construya un autómata finito que reconozca a L(Colina). Explique lo que hace.

1.c) [17 pts] Encuentre el autómata finito mínimo para L(Colina). Escriba los pasos intermedios en la construcción para que muestre cómo aplica los algoritmos.

1.d) [5 pts] Dibuje el autómata finito mínimo de L(NoColina) que es el lenguaje de las hilera que no representan concavidades. Recuerde que para obtener el autómata complementario es necesario que el autómata determinista ya tenga todas las transiciones para todo el alfabeto Σ.

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

1) [33 pts] Versión [B].

1.a) [11 pts] Dibuje el autómata no determinista "1i0p" que rechaza las hileras que tienen una cantidad par de unos o una cantidad impar de ceros. Use el alfabeto Σ = { 0 1 a b }. Explique lo que hace.

1.b) [6 pts] A partir de su autómata no determinista "1i0pN" obtenga la tabla del autómata determinista "1i0p" equivalente. Escriba los pasos intermedios en la construcción para que muestre cómo aplica los algoritmos.

1.c) [11 pts] Minimice su autómata "1i0p". Escriba los pasos intermedios en la construcción para que muestre cómo aplica los algoritmos.

1.d) [5 pts] Dibuje el autómata finito mínimo de L(No1i0p) que es el lenguaje de las hilera que no son aceptadas por "I". Recuerde que para obtener el autómata complementario es necesario que el autómata determinista ya tenga todas las transiciones para todo el alfabeto Σ.

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

2) [33 pts] Versión [A]. str = "[] () [[[]]] ((())) [([ ([( )]) ])]";

2.a) [0 pts] Escriba una gramática LL(1) que sirva para generar todas las hileras de paréntesis redondos y cuadrados anidados, similares a la hilera "str" que se muestra arriba.

2.b) [33 pts] Escriba un programa C++ que reciba como entrada un archivo C++ y determine si sus paréntesis están correctamente anidados. Implemente los métodos que corresponden a las producciones de la clase Analizador_Sintactico de la tercera tarea programada. Use Lex para implementar el analizador léxico. Explique lo que hace.

2) [33 pts] Versión [B].

Escriba un programa C++ que reciba como entrada un archivo C++ y determine si los corchetes { } están correctamente a anidados. Implemente los métodos que corresponden a las producciones de la clase Analizador_Sintactico de la tercera tarea programada. Use Lex para implementar el analizador léxico. Recuerde que si los corchetes aparecen dentro de comentarios [ /* */ // ] o dentro de hileras [".{.}.." '{' '}' ] su analizador léxico no debe tomarlos en cuenta. Explique lo que hace.

3) [33 pts] Considere la gramática G que contiene estas producciones para los no terminales { A B C D X }:

    A -> A | B | C | D
    B -> A | B | C | D ε
    C -> A | B | C | A B * | d
    X -> A | B | C | D ε

3.a) [18 pts] Encuentre una gramática G' equivalente a G en la que no haya producciones innecesarias. Además, G' debe servir para obtener un programa que reconozca el lenguaje L(G). Explique lo que hace.

3.b) [15 pts] Escriba un programa C++ que reconozca L(G). Implemente los métodos que corresponden a las producciones de la clase Analizador_Sintactico de la tercera tarea programada incluyendo el que obtiene el siguiente token de preAnálisis().

Soluciones

$[/\]$