Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inductive definition of a palindrome

  1. May 23, 2010 #1
    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 gonna 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.
     
  2. jcsd
  3. May 24, 2010 #2
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook