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 2001

$[\/]$

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 cuatro preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Considere la expresión regular (x|y)*y(y|x)(y|x)(y|x)

1.a) [5 pts] Haga el diagrama de un autómata no determinista que reconozca esta expresión regular.

1.b) [15 pts] Haga el diagrama de un autómata determinista que reconozca esta expresión regular.

1.c) [5 pts] ¿Qué puede decir sobre la cantidad de estados que se necesitan para reconocer esta expresión regular? ¿Cuántos estados se necesitarían en el autómata determinista si al final hubiera "n" términos (y|x) en lugar de tres?

1.d) [8 pts] Escriba una gramática para esta expresión regular.

2) [33 pts] Cuando se usa la notación prefija para expresiones aritméticas el operador aparece antes que sus operandos. Por ejemplo, x-y se escribe con el símbolo menos adelante: -xy.

2.a) [22 pts] Construya un esquema de traducción dirigido por sintaxis que permita traducir expresiones aritméticas de notación infija a notación prefija (para simplificar su trabajo asuma que los números usados son de un solo dígito y que los operadores son suma y resta).

2.b) [11 pts] Muestre cómo funciona su esquema en la expresión 9-5+2. Para esto, haga el árbol de análisis sintáctico, y decórelo apropiadamente.

3) [33 pts] El lenguaje C tiene una instrucción con la siguiente forma: for ( exp₁; exp₂; exp₃ ) { stmt }

3.a) [11 pts] Haga un diagrama en el que muestre cómo debe quedar compilado este código.

3.b) [22 pts] Escriba un esquema de traducción por sintaxis que transforme un ciclo for en código objeto para una máquina de pila.

4) [33 pts] Dos expresiones regulares son equivalentes cuando tienen el mismo autómata determinista mínimo, salvo cambio en el nombre de los estados.

4.a) [7 pts] Construya el autómata determinista mínimo para la expresión (x|y)* .

4.b) [13 pts] Construya el autómata determinista mínimo para la expresión (y*(ε|x))* .

4.c) [13 pts] Muestre que esas dos expresiones regulares son equivalentes.

Soluciones

$[/\]$