## Question 1

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

1. 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

```
2. 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 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;
}
}

private Buffer b;
...

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

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

private Buffer b;
...

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

public void run() {
...
info = b.get();
...
}
}
```
Note that the wait() command is used in the methods of Buffer, not in run(). It would make no sense to use wait() in run() (and it would also give a compilation error).

## 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).
```