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 2007

$[\/]$

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] Obtenga el NFA para la expresión regular ((a?+b?)*)**c

1.a) [3 pts] Obtenga una autómata que reconozca el lenguaje definido por esta expresión regular. Nombre a los estados de su autómata usando letras minúsculas.

1.b) [15 pts] Obtenga un autómata determinista a partir de este autómata. Escriba los pasos intermedios en la construcción para que muestre cómo aplica el algoritmo para hacerlo.

1.c) [15 pts] Minimice su autómata determinista. Escriba los pasos intermedios en la construcción para que muestre cómo aplica el algoritmo para hacerlo.

1.d) [0 pts] Obtenga una expresión regular para el lenguaje del autómata óptimo. Justifique su respuesta.

2) [33 pts] El estándar para nombrar archivos MP3 es poner primero el número de canción, luego el autor y al final el nombre de la canción, separando esos campos con un guión "-".

2.a) [0 pts] Escriba 2 ejemplos de nombres para archivos MP3.

2.b) [5 pts] Escriba un patrón JavaScript que permita determinar si el nombre de un archivo es un nombre estándar de canción.

2.c) [11 pts] Dibuje un autómata finito "AF" que reconozca el lenguaje de los nombres de archivos (ignore la extensión .mp3). Agrupe en clases todas los números y letras. Defina los tokens que su autómata reconoce.

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

2.e) [0 pts] Dibuje el diagrama de "M".

3) [33 pts] abbb babb bbab bbba

3.a) [0 pts] Diseñe una autómata finito que acepte hileras en las que la cantidad de letras "b" es 3 veces la cantidad de letras "a". Muestre cómo funciona con una hilera de al menos 5 letras.

3.b) [22 pts] Escriba una gramática que sirva para generar hileras en las que la cantidad de letras "b" es 3 veces la cantidad de letras "a". Muestre que sirve con una hilera de al menos 5 letras.

3.c) [11 pts] Si su gramática es ambigua, demuéstrelo. Si no lo es, escriba un gramática equivalente que sí sea ambigua. Demuéstrelo.

4) [33 pts] Considere el siguiente bloque de código, escrito en Haskell:

dohanoi(0, _, _, _) = [] dohanoi(n, from, to, using) = dohanoi(n - 1, from, using, to) ++ [(from, to)] ++ dohanoi(n - 1, using, to, from) hanoi(n) = dohanoi(n, 1, 3, 2)

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

4.b) [0 pts] Declare la clase Token que contiene el token y el lexema que se usaría en la implementación de un compilador para el lenguaje Haskell.

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

4.d) [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++ o Java un analizador sintáctico que use ese analizador léxico para determinar si un programa Haskell es sintácticamente correcto.

Soluciones

$[/\]$