Consider the alphabet Σ = {z, y, z). Recall that a strings of length k over Σ can be written as s = $182 Sk where cach s

[answerhappygod]

1 (37.01 KiB) Viewed 22 times

Consider the alphabet Σ = {z, y, z). Recall that a strings of length k over Σ can be written as s = $182 Sk where cach s; E. Define the set S recursively as follows: (Basis Step) The strings xyz, yzz, zzy are in S. • (Recursive Step) For any w S, the strings ryzw, zywz, xwyz, wryz are all in S. (i) Find all elements in S of length less than or equal to 8. 2 (ii) Prove by structural induction that every element w ES has a length (w) divisible by 3. [Hint: If a number mEN is divisible by 3, then there exists an n N such that m = 3n.]