CI-1322 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II Semestre 2006

$[\/]$

CI-1322 Autómatas y compiladores

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

1) [33 pts] Considere la siguiente gramática:

X → ( L + p )
L → q + L
L → q

1.d) [13 pts] Construya el autómata LALR(1) para esta gramática.

1.b) [7 pts] La tabla LALR(1) de esta gramática tiene al menos un conflicto. Para cada conflicto de la tabla explique de qué tipo es y también diga por qué se da.

1.c) [13 pts] Modifique la gramática de tal manera que reconozca el mismo lenguaje y no presente conflictos en la tabla LALR(1). Justifique las modificaciones hechas a la gramática y verifique su nueva gramática construyendo las nuevas tablas LALR(1).

2) [33 pts] Considere el lenguaje L(G) definido de la siguiente manera:

L(G) = { aⁿ b^r c^r dⁿ / n>0 & r>0 }

2.a) [5 pts] Escriba una gramática libre de contexto G para L(G).

2.b) [14 pts] Calcule las tablas LL(1) para G. Si su gramática no es LL(1), corríjala para que lo sea.

2.c) [14 pts] Muestre cómo se procesa la hilera "aabbbcccdd" si se usan las tablas que usted calculó en el punto anterior.

3) [33 pts] Considere la siguiente gramática libre de contexto G:

    !  -> a 6
    6  ->   9 | O
    9  ->   M | U
    M  ->   R | G
    U  ->   C | A
    R  -> b I
    C  -> a E
    I  ->   G
    E  ->   C | A
    G  ->   L
    A  ->   L
    L  ->   9 | O
    O  -> b S
    S  -> ε

3.a) [1 pts] Dibuje el autómata finito para la gramática G.

3.b) [10 pts] Obtenga el autómata finito determinista D a partir del diagrama de estados de G. Incluya el diagrama de estados del autómata finito.

3.c) [10 pts] Obtenga el autómata finito determinista M minimizando D. Incluya el diagrama de estados de M.

3.d) [12 pts] Muestre cómo reconoce M las siguientes hileras:

a b b b
a a b a

Explique lo que ocurre con cada una de estas hileras.

Soluciones

$[/\]$