Homework Help: Finite Definition of Languages problem

1. May 28, 2012

EonsNearby

1. The problem statement, all variables and given/known data
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)

2. Relevant equations

3. 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?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted