Exercise 1

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

   • Base
     • Case x = lambda: n_a(x) = n_b(x) = 0
     • Case x = aba: n_a(x) = 2 and n_b(x) = 1

   • Inductive case. Let x = aybza, with y, z in L(G). Then n_a(x) = n_a(y) + n_a(z) + 2, while n_b(x) = n_b(y) + n_b(z) + 1. By inductive hypothesis, n_a(y) = 2 n_b(y), and n_a(z) = 2 n_b(z). Hence n_a(x) = 2 n_b(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. L₁ is context free. A grammar generating L₁ is the following:

      S -> T | UV
      T -> aTc | B
      B -> bB | lambda
      U -> aUb | lambda
      V -> bVc | lambda
   

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

3. L₃ is context free. A grammar generating L₃ is the following:

      S -> UV
      U -> aUb | lambda
      V -> cVd | lambda
   

Exercise 5

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.