Exercise 1

1. R is an equivalence relation. In fact, x+y is an even number iff x+y = 2n for some n. Then the relation is reflexive, because x+x = 2x. Simmetry follows from the commutativity of +. As for transitivity, observe that x+y = 2n and y+z = 2m imply x+z = 2(m+n-y). The corresponding partition is constituted by the odd and the even numbers.
2. R is not an equivalence relation, because transitivity is not satisfied. As a counterexample, consider x = 1, y = 10 and z = 19.
3. R is an equivalence relation. Let us denote by rep(x) the decimal representation of x, and by all_but_last(rep(x)) the representation of x without the last digit. Then x R y iff all_but_last(rep(x)) = all_but_last(rep(y)). Since = is an equivalence relation, we have that also R is. As for the partition, note that all_but_last(rep(x)) represents the quotient of the integer division of x by 10. Hence the generic n-th element of the partition will be P_n = { x | x div 10 = n } (where div represents the integer division).
   Note: the first part of this question could also be solved by observing that x and y are related iff x div 10 = y div 10.

Exercise 2

• Proof that L is contained in L'. This is equivalent to say that

  for all x in L, x is in L'

  We prove the statement by structural induction on L.
  • Base: abcc is in L', infact it is of the form aⁿbc²ⁿ when we take n = 1.
  • Inductive step: Take a generic x in L and assume (inductive hypothesis) that x is in L'. Then x is of the form a^kbc^2k for some k > 0. Observe now that the string axcc is of the form aa^kbc^2kcc, i.e. a^k+1bc^2(k+1) with k+1 > 0. Hence axcc is also in L'.
  
  
• Proof that L' is contained in L. This is equivalent to say that

  for all x in L', x is in L.

  We prove the statement by induction on n. (The proof just follows the reverse reasoning of the above one.)
  • Base: for n = 1, the string aⁿbc²ⁿ is abcc, hence it is in L.
  • Inductive step: For a generic k > 0, assume that x = a^kbc^2k is in L. Then the string a^k+1bc^2(k+1) is also in L, because it is equal to axcc.

Exercise 3

1. One possible solution is: ((1+2+...+9)(0+1+...+9)^*)^*(0+2+4+6+8).
2. One possible solution is: (a+c)^*b(a+c)^*.
3. One possible solution is: (ab)^*ab.
4. One possible solution is: ((a+c)(a+c))^*.