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

Problem with this defintion is that we are starting with empty string so this definition will only generate palindromes of even length and palindromes like:101 will not be generated here.

So basis step must have :

Empty string and the 1 element palindromes: 0 and 1.

Recursive step stays the same.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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