Question

Give a recursive definition of the set of bit strings thatx are palindromes.

Short answer

The recursive definition of reversal of strings is derived.

Step-by-step solution

Define recursive and reversal of the string

The recursive function is one that have its values at some specific points obtained by some previous points. Consider the example for the recursive function f(k) = f (k - 2) + f (k - 3) is define over the non-negative integer.

The string is the set of numbers for exampleabcdis the string where all four variables can take up any values.

Consider the reversal $w^R$of the string w is the string written in reverse order.

Find a recursive definition

The recursive definition of the set of bit string that are palindromes is shown below.

First define a set of which is the set of all palindromes.

Basis step: $\lambda \in p$.

Second basis step: $\lambda \in p$when $\lambda \in \sum _{}$.

Recursive step: $\mathrm{xpx}\in \mathrm{p}\mathrm{if}\mathrm{x}\in \underset{}{\sum \mathrm{and}\mathrm{p}\sum _{}\mathrm{p}}$.

Here $\lambda$is empty string and $\sum _{}$is the set of alphabet.

Therefore, the recursive definition of reversal of strings is derived.