Examen #1

1) [25 pts] Gramáticas y autómatas.

1.a) [5 pts] Defina dos gramáticas libres de contexto que generen el lenguaje L = {abc, aabbcc}.

1.b) [5 pts] Pruebe o refute matemáticamente solo dos de las siguientes identidades para expresiones regulares:
      a. (r+s)* = r*+s*       b. (ss+r)* = s*(s+r)*       c. (r*)* = r*

1.c) [15 pts] Haga el diagrama de un autómata que reconozca hileras en que aparece algún cero antes de algún uno. Luego transforme ese autómata en una expresión regular.

2) [25 pts] Sistema para dar formato a programs Pascal.

2.a) [10 pts] Exponga, en pocas palabras, dos maneras diferentes en que se puede construir un programa que tome programas fuentes Turbo Pascal, y les de formato de acuerdo a las Convenciones de Programación. Escoga un lenguaje diferente para cada una de las dos opciones.

[DiM­88]

Di Mare, Adolfo: Convenciones de Programación para Pascal, Reporte Técnico ECCI­01­88, Proyecto 326­86­053, Escuela de Ciencias de la Computación e Informática (ECCI), Universidad de Costa Rica (UCR), 1988.       http://www.di-mare.com/adolfo/p/convpas.htm

2.b) [10 pts] Compare las opciones que expuso en el punto anterior.

2.c) [5 pts] Defina dos situaciones en que resulta mejor usar un lenguaje de propósito específico, como Lotus 123 o Microsoft Excel, en lugar de uno de propósito general, como Pascal o C++. Haga referencia a su exposición en el punto anterior.

3) [25 pts] Examine la siguiente declaración Pascal:

VAR
  M: ARRAY[1..5] OF
       ARRAY[6..10] OF
          ARRAY[11..15] OF REAL;

3.a) [10 pts] De acuerdo a las reglas de Pascal, haga un diagrama de cómo queda almacenada en memoria esta matriz tridimensional. Luego escriba tres ciclo anidados para que en la posición M[i,j,k] quede almacenado el valor sin(i)+cos(j*j)+tan(k*k*k).

3.b) [5 pts] Reordene el acceso a la matriz M[] de manera que el acceso a la memoria se haga en forma secuencial, y no salteada. Recuerde los consejos de [Man­96a] y [Man­96b].

3.c) [5 pts] Explique por qué y cómo se puede lograr mejorar el rendimiento de esta sección de código, sustituyendo la siguiente instrucción de asignación:
      M[i,j,k] = sin(i)+cos(j*j)+tan(k*k*k).

3.d) [5 pts] Implemente las ideas que expuso en el punto anterior.

4) [25 pts] Escriba la función recursiva Suma(a,b:INT), que calcula la suma de dos números no negativos "a" y "b", invocando a las funciones de biblioteca Pred() y Succ(), que calculan el predecesor y el sucesor de un número entero.

      Muestre los registros de activación que componen la pila de ejecución del programa cuando hay pendientes de retornar tres llamados de la rutina Suma(), incluyendo dos llamados recursivos. Explique el efecto que tiene el pasar por copia y por referencia a los parámetros "a" y "b".

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1998
Derechos de autor reservados © 1998