HQ1. [Page limit 2 pages] Consider the following recursive definition of a language L over the alphabet {a,-,+,*}.
* a is in L.
* If strings x and y are in L then the strings x+y and x*y are in L.
* If string z is in L then the string -z is in L.
* Nothing else is in L.

(a) Prove that if x is a string in L then (i) x does not contain the substring '++' and (ii) x does not end with + and (iii) x does not begin with +. Use induction on the length of x (no marks for level-1).

(b) Prove that if x is a string in L then x does not contain the substring '++'. Use proof by induction on the length of x. If you are unable to prove this statement then explain why.