## Exercise 1

1. By structural induction on the way a string x in L(G) can be generated:

• Base
• Case x = lambda: na(x) = nb(x) = 0
• Case x = aba: na(x) = 2 and nb(x) = 1

• Inductive case. Let x = aybza, with y, z in L(G). Then na(x) = na(y) + na(z) + 2, while nb(x) = nb(y) + nb(z) + 1. By inductive hypothesis, na(y) = 2 nb(y), and na(z) = 2 nb(z). Hence na(x) = 2 nb(x).

2. L does not coincide with L(G). In fact, baa is in L but not in L(G).

3. The grammar is ambiguous, because the string aba can be generated in two different ways, namely recursively, by using the second production, or directly, by using the third production. To eliminate the ambiguity it is sufficient to eliminate the third production. Hence an equivalent unambiguous grammar is the following:
S -> lambda | aSbSa

## Exercise 2

1. L1 is context free. A grammar generating L1 is the following:
S -> T | UV
T -> aTc | B
B -> bB | lambda
U -> aUb | lambda
V -> bVc | lambda

2. L2 is not context free. It's possible to prove it by using the pumping lemma. (Proof omitted.)

3. L3 is context free. A grammar generating L3 is the following:
S -> UV
U -> aUb | lambda
V -> cVd | lambda

## Exercise 5

L is recursively enumerable, but not decidable. In fact:
1. L can be recognized by a TM M' such that, given input x, if x = e(M) for some M then M' emulates the TM M on input 00. If x is not the encoding of any TM then M' crashes.
2. L is not recursive because the property "M accepts 00" is not trivial, hence by the theorem of Rice L cannot be recursive.