Definition:Palindrome/Definition 2
Jump to navigation
Jump to search
Definition
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)$.
Also see
Linguistic Note
The word palindrome derives from the Ancient Greek παλίνδρομος (palíndromos), meaning running back again.
This is formed from πάλιν (pálin), meaning back, again, and back again, and δρόμος (drómos), meaning running, race, and racecourse.
Sources
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: Exercises: $1.3$