Proving facts about recursively defined sets of strings. (a) Consider a set of strings defined recursively as follows: • Base case: a es • Recursive rule: if x ∈ S then, xb ∈ S (Rule 1) xa ∈ S (Rule 2) Prove that every string in S begins with the character a.
(b) Consider a set of strings defined recursively as follows: • Base case: a es • Recursive rules: if x ∈ S then,
xb ∈ S (Rule 1)
bx ∈ S (Rule 2) Prove that every string in S contains exactly one a.