Inductive definition of a palindrome

[OptimusPwn]

A palindrome is a string that reads the same left to right as right to left (as in RADAR). Give an inductive definition of the set of all palindromes.

I am having trouble with this problem. So far I think I have the basis, which is an if statement that says, if length of string is even, then the empty string is in S(I'm going to call the string S), else, x is in S. THEN I Build from there on, although I really have no idea how to do this. Please, help will be greatly appreciated.

Thanks.

 

[Coin]

Homework problem? Anyway I think what you want to do is something like

S -> xSx
S -> x
S -> ε

Where "x" is "any letter of the alphabet". So in other words the empty string is a palindrome, a one-letter string is a palindrome, and any palindrome with the same single character added at both the beginning and end is also a palindrome.