## Question 1

1. 25 * 3   no
2. 5 ^ 2 * 3   yes
3. (5 ^ 2) * 3   no
4. 5 * 2 * 3   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 ^ Exp      Num * Exp
/|\    |        |    /|\
/ | \   |        |   / | \
Num * Exp Num      2 Exp ^ Exp
|     |  |           |     |
|     |  |           |     |
2    Num 4          Num   Num
|              |     |
|              |     |
3              3     4

```
2. An equivalent non-ambiguous grammar where ^ has precedence over * is the following:
```   Exp ::= Exp * A | B
A ::= C ^ A | Num
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 ::= Num * A | Num | (Exp)
Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
```

## Question 3 (Concurrency in Java)

```  class Account {

private int balance;

public Buffer(int initialDeposit) { balance = initialDeposit; }

public synchronized int getBalance() {
return balance;
}

public synchronized void deposit(int amount) {
if (amount < 0)
error(1) % the amount to deposit should be non negative
else {
balance = balance + amount;
notifyAll();
}
}

public synchronized void withdraw(int amount) { //we omit the treatment of interruptedExeption
if (amount < 0)
error(1) % the amount to withdrow should be non negative
else {
while (balance < amount) wait();
balance = balance - amount;
}
}
}

Account a;
...
public void run() {
...
a.deposit(x);
...
a.withdraw(y); // no need to test that the balance is greater than or equal to the amount to withdraw
...
}
}
```
Note that the wait() command is used in a method of Account, 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 max(x,y) = if x > y then x else y;

fun heights(leaf x) = leaf 1
| heights(node(t1,x,t2)) = let val (h1,u1) = heights t1
and val (h2,t2) = heights t2
in node(u1, max(h1,h2)+1, u2)
end;
```
Another alternative solution, perhaps more elegant, is the following:
```   fun root (leaf x) = x
| root (node(t1,x,t2)) = x;

fun heights(leaf x) = leaf 1
| heights(node(t1,x,t2)) = let val u1 = heights t1
and val u2 = heights t2
in node(u1, max(root u1, root u2) + 1, u2)
end;
```

## Question 5 (Prolog)

```   divisor_and_rest(M,N,X,Y) :- nat(X,N), nat(Y,N), N is M * X + Y.

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

## Question 6 (Prolog)

```   conc([],[]).
conc([X|L],K) :- conc(L,M), append(X,M,K).
```