CI-1322 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II Semestre 2003

$[\/]$

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

1) [33 pts] Considere el siguiente bloque de código, escrito en un dialecto de Prolog [CM-83] (pg 136-137):

hanoi(N) :- move(N, left, center, right). move(0,_,_,_) :- !. move(N,A,B,C) :- M is N-1, move(M,A,C,B), w(A,B), move(M,C,B,A). w(From,To) :- write([move, from, From, to, To]), nl.

1.a) [0 pts] Diga cuáles son los tokens y cuáles son los lexemas en este bloque de código.

1.b) [13 pts] Escriba una gramática que genere la mayor parte de los programas similares éste.

1.c) [20 pts] Suponga que usted ya cuenta con un analizador léxico getNextToken() que retorna los tokens para procesar hileras generadas por su gramática. Implemente en C++ un analizador sintáctico que use ese analizador léxico para determinar si un programa Prolog es sintácticamente correcto.

2) [33 pts] r = ( (0|1)* 1 (0|1)* | (1|0)* 0 (1|0)* ) ?

2.a) [11 pts] Para la expresión regular "r" construya el autómata no determinista "N" que reconoce L(r).

2.b) [11 pts] Obtenga a partir de "N" un autómata determinista "D" que reconoce el mismo lenguaje que "N". Dibuje el diagrama de "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. Dibuje el diagrama de "M".

3) [33 pts] Considere la expresión (a + (b c* d) )* en la que el operador + denota la unión y el operador * denota la cerradura de Kleene. Además, la concatenación se denota poniendo las expresiones juntas, como ocurre con (b c* d). Los paréntesis sirven para cambiar el orden de evaluación de la expresión.

3.a) [0 pts] Para esta expresión indique cuáles son los tokens y lexemas que un analizador léxico retornaría.

3.b) [13 pts] Escriba una gramática que sirva para generar expresiones similares a ésta. Recuerde que la cerradura de Kleene tiene mayor precedencia que la concatenación. Además, la concatenación tiene mayor precedencia que la unión. También tome en cuenta que todos estos operadores binarios son asociativos a la izquierda.

3.c) [20 pts] Suponga que usted ya cuenta con un analizador léxico que retorna los tokens para procesar hileras generadas por su gramática. Implemente en C++ un analizador sintáctico que use ese analizador léxico para determinar si una de estas expresiones es correcta sintácticamente.

4) [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 estén definidas las transiciones para todos los estados en todos los símbolos del alfabeto Σ.

4.a) [0 pts] Explique la diferencia entre una "sub-hilera" y una "sub-secuencia".

4.b) [5 pts] Haga el diagrama del autómata finito L:bcc que reconozca hileras en el alfabeto Σ = {b,c} en las que aparece la subsecuencia "bcc".

4.c) [14 pts] Encuentre el autómata noL:bcc que reconoce el lenguaje complementario de L:bcc, esto es, el autómata que cumple estas condiciones: (Σ^* = L:bcc U noL:bcc) & (Σ^* - L:bcc = noL:bcc) & (L:bcc ∩ noL:bcc = Θ)

4.d) [14 pts] Minimice el autómata noL:bcc. Muestre el diagrama final del autómata minimizado.

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

Soluciones

$[/\]$