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 2007

$[\/]$

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] En la empresa TurboMan tienen una máquina troqueladora robot que se descompone mucho, porque los operarios le mueven la palanca y la ponen a hacer movimientos indebidos. Por ejemplo, ya les han dicho que si está para atras ←, los movimientos válidos son para arriba ↑ o para abajo ↓, pero no se puede ir hacia adelante →. Además, en cualquier momento se puede poner el taladro Θ.

1.a) [11 pts] A usted le piden que conecte la troqueladora de TurboMan con la computadora de manera que la computadora analice los comandos { ← ↑ ↓ → Θ} y determine si al ejecutarlos se quiebra la máquina. Diseñe un autómata que haga el trabajo. Use la tecnología vista en el curso (a menos que quiera sacar 0 puntos).

1.a) [11 pts] Muestre un ejemplo de al menos 10 comandos que su autómata rechazará porque quiebran la máquina. También muestre un ejemplo de 5 comandos que la máquina sí puede procesar.

1.c) [11 pts] Escriba un programa C++ que resuelva el problema.

2) [33 pts] Considere la gramática G que contiene las siguientes producciones:

    S ==> E 1     S ==> 2 E 3
    E ==> 4       S ==> X 3
    X ==> 4       S ==> 2 X 1

2.a) [11 pts] Calcule y dibuje el autómata LR(1) de esta gramática.

2.b) [6 pts] Haga la tabla de análisis sintáctico LR(1).

2.c) [0 pts] Explique por qué esta gramática es o no LR(1).

2.d) [0 pts] Dibuje el autómata LALR(1) de la gramática anterior.

2.e) [11 pts] Haga la tabla de análisis sintáctico LALR(1).

2.f) [5 pts] Explique por qué esta gramática es o no LALR(1).

3) [33 pts] Es bien sabido que si ya se cuenta con un autómata determinista (sin movimientos ε) que reconoce el lenguaje L, es fácil obtener el autómata complementario, que reconoce Σ^*-L: basta cambiar en L los estados finales por no finales, y los no finales por finales (siempre y cuando la tabla de transiciones esté completa).

3.a) [11 pts] Haga el diagrama del autómata determinista L0i0 que reconozca hileras en el alfabeto Σ = {0,1} que comienzan y terminan con cero, pero que tienen una cantidad impar de unos.

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

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

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

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

Soluciones

$[/\]$