Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
II Semestre 2002
[<=] [home] [<>] [\/] [=>]
CI-1322 Autómatas y compiladores

Examen #1 [solución]

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

 

1) [33 pts] (a+b) <: (c*D**F) <:= H ** i ** j

En esta expresión se usa el operador ternario para denotar rangos, que evalúa cada término y retorna "true" si la expresión del centro está entre las de los extremos.

1.a) [6 pts] De un ejemplo de cada una de los posibles rangos que se pueden expresar con el operador ternario de rangos.

1.b) [11 pts] Extienda la gramática de expresiones para que incluya los operadores ternarios de rangos. Al formar expresiones también permita que se use el operador de exponenciación "**", pero asegúrese de que tenga mayor precedencia que los operadores multiplicativos y de que sea asociativo a la derecha. Su gramática debe ser recursiva izquierda.

1.c) [5 pts] Transforme su gramática es una gramática que no sea recursiva izquierda.

1.d) [11 pts] Haga una derivación de una hilera "w" en la que aplique por lo menos 10 producciones de "G" y en la que se usen operadores ternarios, de exponenciación multiplicativos y aditivos.

 

2) [33 pts] Considere la expresión regular r = (a b) ( (a|b)+ b (b|c)+ )

2.a) [11 pts] Construya el autómata no determinista "N" que reconoce el lenguaje de "r".

2.b) [11 pts] Obtenga a partir de "N" un autómata determinista "D" que reconoce el mismo lenguaje que "N". Haga el diagrama del autómata "D".

2.c) [11 pts] Obtenga a partir de "D" un autómata determinista "M" que reconoce el mismo lenguaje que "D", pero que además es óptimo porque tiene una cantidad mínima de estados. Haga el diagrama del autómata "M".

 

3) [33 pts] En posfijo los operandos aparecen antes de los operadores: ab+c*

3.a) [11 pts] Escriba una gramática que genere expresiones aritméticas en posfijo. Los operadores que puede usar son los aditivos y multiplicativos.

3.b) [11 pts] Haga una derivación de una hilera "w" en L(G) en la que aplique por lo menos 10 producciones de "G".

3.c) [11 pts] Escriba un esquema de traducción por sintaxis que transforme une expresión escrita en posfijo a una escrita en infijo. Agregue todo los paréntesis que quiera.

 

4) [33 pts] Considere el siguiente bloque de código, escrito en un lenguaje similar a C++: 

for (numero = 1; numero <= N; ++numero) {
    suma = 0;
    temp = numero;
    while ( temp != 0 ) {          // suma de dígitos
        digito = temp %  10;       // al cubo
        suma   = suma + (digito * digito * digito);
        temp   = temp /  10;
    }
    if (suma == numero) {
        cout << numero << " Suma de sus dígitos al cubo " << suma << endl;
    }
}

4.a) [0 pts] Escoga los nombres para los tokens que usará para contestar estas preguntas.

4.b) [11 pts] Diga cuáles son los tokens y cuáles son los lexemas en este bloque de código.

4.c) [11 pts] Escriba una gramática que genere la mayor parte de los programas similares éste.

4.d) [11 pts] Escriba un programa Lex que sirva para obtener los tokens y lexemas de este lenguaje.

 

Soluciones

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2002
Derechos de autor reservados © 2002
[home] <> [/\]