Recall that a bit string is a string using the alphabet {0, 1}. A palindrome is

Question

Recall that a bit string is a string using the alphabet {0, 1}. A palindrome is a string that is equal to the reversal of itself. Consider the following recursive definition of a palindrome: Basis Step: (the empty string) is a palindrome. Recursive Step: If w is a palindrome and x {0, 1}, then xwx is a palindrome. There is a problem with this definition. Identify and state the problem. Then fix the problem by providing a new correct recursive definition. Hint: Write down some palindromes that are short in length and check if they meet the recursive definition.

Explanation / Answer

Base case is incorrect. We start with empty strings and add xx to both ends of the strings in each step

BUt this will give only strings of even length. Strings like: 0,1 are also palindrome but this recursive defintion will not generate them.

So we modify base case as:

We start with empty string,0 ,1 as the three palindromes.

Recursive step is correct and remains as before.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.