Equivalence of Definitions of Palindrome
Theorem
The following definitions of the concept of Palindrome are equivalent:
Definition 1
A palindrome is a string which stays the same when reversed.
Definition 2
A palindrome is a string defined as follows:
- $(1): \quad$ The null string $\epsilon$ is a palindrome.
- $(2): \quad$ If $a$ is a symbol, then the string $a$ is a palindrome.
- $(3): \quad$ If $a$ is a symbol and $x$ is a palindrome, then $axa$ is a palindrome.
- $(4): \quad$ Nothing is a palindrome unless it has been created by one of the rules $(1)$ to $(3)$.
Proof
The proof proceeds by strong induction on the length of a string.
For all $n \in \N$, let $\map P n$ be the proposition:
- Every palindrome $S_n$ of length $n$ is a palindrome by definition $1$ if and only if it been generated by definition $2$.
For clarity, let us denote by $\sqbrk {abc \ldots}$ denote the string formed from the symbols $a, b, c, \ldots$
Basis for the Induction
$\map P 0$ is the case:
- Every palindrome $S_0$ of length $0$ is a palindrome by definition $1$ if and only if it been generated by definition $2$.
By definition $2$ of a palindrome:
- $(1): \quad$ The null string $\epsilon$ is a palindrome.
This is the only string of length $0$.
$\epsilon$ is seen vacuously to be a palindrome by definition $1$.
Thus $\map P 0$ is seen to hold.
$\map P 1$ is the case:
- Every palindrome $S_1$ of length $n$ is a palindrome by definition $1$ if and only if it been generated by definition $2$.
Let $a$ be an arbitrary symbol.
By definition $2$ of a palindrome:
- $(2): \quad$ If $a$ is a symbol, then the string $\sqbrk a$ is a palindrome.
But the string $\sqbrk a$ consisting just of symbol $a$ reads the same backwards as forwards.
Thus $\map P 1$ is seen to hold.
We use $\map P 0$ and $\map P 1$ together to form the basis for the induction.
Induction Hypothesis
Now it needs to be shown that if $\map P j$ is true, for all $j$ such that $0 \le j \le k$ and $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
This is the induction hypothesis:
- Every palindrome $S_j$ of length $j$ such that $j \le k$ is a palindrome by definition $1$ if and only if it been generated by definition $2$.
from which it is to be shown that:
- Every palindrome $S_{k + 1}$ of length $k + 1$ is a palindrome by definition $1$ if and only if it been generated by definition $2$.
Induction Step
This is the induction step:
Let $x$ be a palindrome of length $k - 1$ according to either definition $1$ or definition $2$.
By the induction hypothesis, $\sqbrk x$ is therefore a palindrome by both definition $1$ and definition $2$.
Let $a$ be an arbitrary symbol.
By definition $2$ of a palindrome:
- $(3): \quad$ If $a$ is a symbol and $\sqbrk x$ is a palindrome, then $\sqbrk {axa}$ is a palindrome.
But $\sqbrk x$ reads the same backwards and forwards.
Hence $\sqbrk {axa}$ reads the same backwards and forwards.
So if $\sqbrk {axa}$ is a palindrome by definition $2$, it follows that $\sqbrk {axa}$ is a palindrome by definition $1$.
Now suppose $\sqbrk y$ is a palindrome of length $k + 1$ according to definition $1$.
That is, $\sqbrk y$ reads the same backwards as it does forwards.
Then the first symbol of $\sqbrk y$ is the same as the last symbol of $\sqbrk y$.
Thus $\sqbrk y$ is of the form $\sqbrk {axa}$ where $\sqbrk x$ is a palindrome of length $k - 1$.
Hence by the induction hypothesis, $\sqbrk x$ is a palindrome of length $k - 1$.
Thus $\sqbrk {axa}$ has been formed from $\sqbrk x$ by an application of rule $(3)$ by definition $2$.
Hence if $\sqbrk y$ reads the same backwards as it does forwards, then it has been created by rule $(3)$.
Thus we have shown that for all $k \in \N$, if $\sqbrk y$ reads the same backwards as it does forwards, then it has been created by one of the rules $(1)$, $(2)$ or $(3)$.
So $\paren {\forall j: 0 \le j \le k: \map P j} \implies \map P {k + 1}$ and the result follows by the Second Principle of Mathematical Induction.
Therefore:
- For all $n \in \N$: every palindrome $S_n$ of length $n$ is a palindrome by definition $1$ if and only if it been generated by definition $2$.
$\blacksquare$
Sources
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: Exercises: $1.3$