Exercise 8.9.3: Characterizing the strings in a recursively defined set.
i About
The recursive definition given below defines a set S of strings over the alphabet (a, b):
• Base case: AES and a € S
• Recursive rule: if x ES then,
• xb ES (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 ES 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 E 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 E 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 E S.