The recursive definition given below defines a set S of strings over the alphabet (a, b):...

Transcribed Image Text:

The recursive definition given below defines a set S of strings over the alphabet (a, b): Base case: A e S and a S Recursive rule: if x = S then, xb S (Rule 1) xba 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 = S if 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 x = 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 x S. Specifically, prove the following statement parameterized by n: For any n 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 = S. The recursive definition given below defines a set S of strings over the alphabet (a, b): Base case: A e S and a S Recursive rule: if x = S then, xb S (Rule 1) xba 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 = S if 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 x = 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 x S. Specifically, prove the following statement parameterized by n: For any n 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 = S.