Inductive definition of a palindrome

  • Thread starter Thread starter OptimusPwn
  • Start date Start date
  • Tags Tags
    Definition
AI Thread Summary
A palindrome is defined as a string that reads the same forwards and backwards, exemplified by the word "RADAR." The discussion focuses on creating an inductive definition for the set of all palindromes. The proposed solution begins with a base case where the empty string is considered a palindrome. It then outlines the inductive steps: a string can be formed by adding the same character to both ends of an existing palindrome, or it can be a single character. This leads to the formal definitions: S can be an empty string (ε), a single character (x), or a string formed by the pattern xSx, where x represents any letter of the alphabet. This structure effectively captures all possible palindromic strings.
OptimusPwn
Messages
3
Reaction score
0
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.
 
Technology news on Phys.org
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.
 
Thread 'Is this public key encryption?'

Thread 'Is this public key encryption?'

I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
View full post »

Similar threads

Python How Can I Combine Slicing and Reversing to Determine Palindromes in Python?
2
Replies
55
Views
6K
C/C++ Max length of substring-palindrome
Replies
1
Views
1K
Writing a recursive function by using optional parameters
Replies
2
Views
2K
Comp Sci How do I think about recursion in programming?
Replies
11
Views
2K
Spaces check in a Palindrome checking recursive algo.
Replies
7
Views
3K
Why isn't my hash set doing a good job?
Replies
19
Views
2K
Comp Sci Check if a String is Palindrome with Java Program | Homework Statement
Replies
12
Views
9K
Proving Injectivity & Surjectivity of f: Palindromes over X
Replies
1
Views
3K
Please critique my program design
Replies
41
Views
5K
MHB TM: Is the given string of the form uu?
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top