The recursive definition given below defines a set of strings over the alphabet (a, b): Base case: S and a es Recursive rule: if Xe S then, o xD e S (Rule 1) xba e S (Rule 2) This problem asks you to prove that the set S is exactly the set of strings over (a, b) which do not contain two or more consecutive a's. In other words, you will prove that x e Sif and only if x does not contain two consecutive a's. The two directions of the "if and only if" are proven separately. (a) Use structural induction to prove that if a string xe S, then x does not have two or more consecutive a's. (b) Use strong induction on the length of a string x to show that if x does not have two or more consecutive a's, then xe S. Specifically, prove the following statement parameterized by n: For any n 2 0, let x be a string of length n over the alphabet (a, b) that does not have two or more consecutive a's, then x e S