- #1

EonsNearby

- 43

- 0

## Homework Statement

A palindrome over an alphabet Ʃ is a string in Ʃ* that is spelled the same forward and backward. The set of palindromes over Ʃ can be defined recursively as follows:

i) Basis: λ and a, for all a that are elements of Ʃ, are palindromes.

ii) Recursive step: If w is a palindrome and a is an element of Ʃ, then awa is a palindrome.

iii) Closure: w is a palindrome only if it can be obtained form the basis elements by a finite number of applications of the recursive step.

The set of palindromes can also be defined by {w | w = w^R }. Prove that these two definitions generate the same set.

(w^R means the reversal of w)

## Homework Equations

## The Attempt at a Solution

I don't have an attempt because I'm not sure how to start the proof. Do I prove this the same way I would prove the associative law of sets, or would I prove this using induction?