Question

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet {a, b} defined inductively as follows: • Base case: the empty word λ and the word a belong to S • Inductive rule: if ω is a string of S then both ω b and ω b a belong to S as well. 1. Prove that if a string ω belongs to S, then ω does not have two or more consecutive a’s. 2. Prove that for any n ≥ 0, if ω is a string of length n over the alphabet {a, b} that does not have two or more consecutive a’s, then ω is a string of S.

Answer 1

Please hit the like button if you find this answer to be helpful. Thank you!