Primera evaluación de Temas Selectos de
Ingeniería en Computación I
Trimestre 2007 Invierno
Problema 1: Escriba un programa
para resolver el problema File
Fragmentation. PS: Prueben
sus programas en el sitio de la UVa.
Problema 2: Escriba un programa
que reciba como entrada estándar una expresión regular y
produzca como
salida una descripción del autómata finito no
determinístico con
transiciones vacías que reconozca cadenas que pertenezcan
al lenguaje
dado por la expresión regular. Una expresión regular
puede usar el
alfabeto de las letras minúsculas, un guión - para la cadena vacía,
paréntesis () para
agrupar, el punto . para
representar la
concatenación, el signo de suma +
para representar la unión y el asterisco * para representar la cerradura
de Kleene. El autómata a la salida debe cumplir la propiedad que
cada
estado tiene a lo sumo dos transiciones de salida. El estado inicial
debe ser el estado 1 y el estado final debe ser el estado F (donde F es
el número total de estados del autómata). Como ejemplo,
si la entrada es a*.b
entonces la salida podría ser la siguiente:
5
1 - 2 - 4
2 a 3
3 - 1
4 b 5
5
donde el primer 5 indica que hay 5 estados, luego hay un renglón
por cada estado (en orden) en el formato p a q b r que quiere decir que
el estado p pasa al
estado q con una a y al estado r con una b. Observe que estos renglones
también pueden estar en los formatos p ó p a q en caso de que el estado
p tenga menos de dos transiciones.