Question 1

1. 1. 2 * 81   no
   2. 2 * (3 ^ 4)   no
   3. (2 * 3 ^ 4)   yes
   4. 2 * 3 * 4   yes

2. There are two kinds of ambiguity:
   1. Associativity of ^
   2. Precedence between * and ^
   An example of the first is:

   
             Exp            Exp
             /|\            /|\
            / | \          / | \
          Exp ^ Exp      Exp ^ Exp
          /|\    |        |    /|\
         / | \   |        |   / | \
       Exp ^ Exp Num    Num Exp ^ Exp
        |     |  |        |  |     |
        |     |  |        |  |     |
       Num   Num 4        2 Num   Num
        |     |              |     |
        |     |              |     |
        2     3              3     4
   
   

   An example of the second is:

   
             Exp            Exp
             /|\            /|\
            / | \          / | \
          Exp * Num      Exp ^ Exp
          /|\    |        |    /|\
         / | \   |        |   / | \
       Exp ^ Exp 4      Num Exp * Num
        |     |           |  |     |
        |     |           |  |     |
       Num   Num          2 Num    4
        |     |              |  
        |     |              |   
        2     3              3     
   
   

3. An equivalent non-ambiguous grammar where ^ has precedence over * is the following:

      Exp ::= Exp * Num | Exp * A | B
        A ::= Num ^ B 
        B ::= C ^ B | C
        C ::= Num | (Exp)
      Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   

   An equivalent non-ambiguous grammar where * has precedence over ^ is the following:

      Exp ::= A ^ Exp | A
        A ::= A * Num | Num | (Exp)
      Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   

Question 2 (Memory management)

Question 3 (Concurrency in Java)

  class Buffer {

      private Information content;
      private boolean empty;

      public Buffer() { empty = true; }

      public synchronized boolean is_empty() {
         return empty;
      }

      public synchronized void put(Information i) { //we omit the treatment of interruptedExeption
         while (!is_empty()) wait();
         content = i; 
         empty = false;
         notifyAll();         
      }

      public synchronized Information get() {
         while (is_empty()) wait();
         empty = true;
         notifyAll();         
         return content; 
      }
   }

   class Producer extends Thread {
       private Buffer b;
       ...

       public Producer(Buffer x){ b = x; }

       public void run() {
               ...
                b.put(info); // no need to test is_empty
               ...
       }
   }

   class Consumer extends Thread {
       private Buffer b;
       ...

       public Consumer(Buffer x){ b = x; }

       public void run() {
               ...
               info = b.get();
               ...
       }
   }

Question 4 (ML)

   fun aux(leaf x, n) = leaf x
     | aux(node(t1, x, t2), n) = node(aux(t1,n+1),n,aux(t2,n+1));

   fun levels(t) = aux(t,1);

Question 5 (Prolog)

   solutions(N,X,Y) :- nat(X,N), nat(Y,N), N is X + Y, factorial(Y,X).

   nat(M,M) :- M >= 0.
   nat(X,M) :- M > 0, N is M - 1, nat(X,N).

   factorial(0,1).
   factorial(Y,X) :- Y > 0, Z is Y - 1, factorial(Z,W), X is W * Y.

Question 6 (Prolog)

   ord_merge(L,[],L).
   ord_merge([],L,L).
   ord_merge([X|L],[Y|M],[X|K]) :- X =< Y, ord_merge(L,[Y|M],K).
   ord_merge([X|L],[Y|M],[Y|K]) :- X > Y, ord_merge([X|L],M,K).