Question

Define a set S recursively as follows: I. BASE: (the empty word), a, and b are in S. II. RECURSION: If s ∈ S, then a. asa ∈ S b. bsb ∈ S III. RESTRICTION: No words are in S other than those derived from I and II above.(a) Give a derivation showing that bab is in S.(b) Give a derivation showing that baab is in S.(c) Use structural induction to prove that every string in S is a palindrome. If it makes things easier, you can use the notation s to denote reversing a word (e.g., abb = bba).(d) Argue that abb is not in S

Answer 1

Answer:

See below

Step-by-step explanation:

a) By the base case, a∈S. By the recursive step, bsb∈S if s∈S. Then, for s=a, bab∈S.

b) By the base case, ∅∈S. By the recursive step, asa∈S if s∈S. Then, for s=∅, a∅a=aa∈S. By the recursive step, bsb∈S if s∈S. Then, for s=aa, baab∈S.

c) Structural induction: We want to prove that s is palindrome for all s∈S.

Inductive basis: If s=a,b or ∅, then s is palindrome because s has either 0 or 1 characters.

Inductive hypothesis: Suppose that r∈S is a palindrome.

Inductive step: We will prove that every element constructed from r using the recursion is also a palindrome. Because of the restriction, all elements of S are constructed in this way, except for the base case. Thus, combining this with the inductive step, we will prove that every element of S is a palindrome.

Let t be an element constructed from r by recursion. Then t=ara or t=brb. If t=ara, then t is a palindrome, because reversing the word (denote the reverse word by capitals) gives T=aRa, with R being the reverse word of r. But r is a palindrome, hence r=R and T=aRa=ara=t. Again, if t=brb, T=bRb=brb=t.

We have completed the inductive step, hence by structural induction, every element of S is palindrome.

d) By recursion and the restiction, the only elements of S of length 3 are aaa,bbb,aba,bab. abb is none of those, hence abb∉S. (note that abb is not a palindrome, so by part c), abb∉S).