Palindrom

Ein Palindrom (von griechisch Παλίνδρομος (palíndromos) „rückwärts laufend“) ist eine Zeichenkette, die von vorn und von hinten gelesen gleich bleibt (wie zum Beispiel das Wort RENTNER). Palindrome müssen nicht immer einen Sinn ergeben, die Zeichenkette muss allerdings von vorne nach hinten und von hinten nach vorne von den verwendeten Zeichen und deren Reihenfolge genau gleich sein.

Verwandt zum Palindrom ist das Ambigramm, bei dem sich meist nach einer 180°-Drehung noch dasselbe Wort ergibt. Gelegentlich werden auch Ananyme fälschlich als Palindrome bezeichnet.

Laut Guinnessbuch der Rekorde von 1997 lautet das längste deutsche Ein-Wort-Palindrom Reliefpfeiler, wobei jedoch das Wort Retsinakanister noch länger ist. Als längstes Wortpalindrom der Alltagssprache gilt das finnische Saippuakivikauppias.

Palindrome müssen nicht zwangsläufig nur aus Buchstaben bestehen. So gibt es etwa Musik-Palindrome, also Musikstücke, die sich vorwärts wie rückwärts gespielt gleich anhören oder Zahlenpalindrome, die von vorn oder hinten gesehen den gleichen Wert ergeben (etwa 2442). Primzahlen wiederum, die, im Gegensatz zu Primzahlpalindromen, rückwärts gelesen neue Primzahlen ergeben (also keine Palindrome sind), nennt man Mirpzahlen. Ferner existieren noch Datums-Palindrome, z. B. der 20. 02. 2002.

Beispiele

Wortpalindrome

• Anna
• Hannah
• Lagerregal / Regallager
• Otto
• Reittier
• Reliefpfeiler
• Rotor
• Noel

Otto, Reittier und Rotor sind zusätzlich Morsecode-Palindrome, da sie ausschließlich aus symmetrischen Morsezeichen bestehen.

Satzpalindrome

• Die Liebe ist Sieger; stets rege ist sie bei Leid.
• Eine güldne, gute Tugend: Lüge nie!
• Erika feuert nur untreue Fakire.
• Ein Esel lese nie.
• Ein Neger mit Gazelle zagt im Regen nie.
• O Genie, der Herr ehre Dein Ego!
• Trug Tim eine so helle Hose nie mit Gurt?
• Regal mit Sirup pur ist im Lager.

Palindrome in der Informatik

In der theoretischen Informatik, genauer: der Theorie der formalen Sprachen, wurde ein mathematischer Formalismus zum Umgang mit Zeichenketten entwickelt.

Die Definition, dass ein Palindrom ein Wort ist, welches rückwärts geschrieben wieder das gleiche Wort ergibt, schreibt sich nun formal so:

Definition

Ein Palindrom ist ein Wort $u\in \Sigma ^{*}$ mit der Eigenschaft

$u=u^{R}$,

wobei $u^{R}$ bedeutet, dass der Operator $.^{R}$ der Spiegelung (bzw. Umkehrung der Reihenfolge) auf das Wort $u$ angewandt wird. Beachte, dass ein Palindrom hier keinen Sinn ergeben muss, das entsprechende Wort muss lediglich symmetrisch um seine Mitte aufgebaut sein, wie der folgende Abschnitt zeigt.

Symmetrische Zerlegung

Dabei gilt

$u=v\,v^{R}=w^{R}\,w$,

falls $|u|$ (Wortlänge) gerade ist, bzw.

$u=v\,c\,v^{R}=w^{R}\,c\,w$,

falls $|u|$ ungerade ist, wobei $v,w\in \Sigma ^{*}$ (endliche Wörter) und $c\in \Sigma$ (ein Zeichen des Alphabets) ist.

Dies sieht man jeweils durch Einsetzen, z. B.:

$u^{R}=(v\,c\,v^{R})^{R}=(v^{R})^{R}\,c^{R}\,v^{R}=v\,c\,v^{R}=u$

beispielsweise kann man

$u={\mbox{GNUDUNG}}$

zerlegen mit

$v={\mbox{GNU}}$ und $c={\mbox{D}}$,

so dass

$u=v\,c\,v^{R}={\mbox{GNU}}\,{\mbox{D}}\left({\mbox{GNU}}\right)^{R}={\mbox{GNUDUNG}}$.

Erkennung von Palindromen

Die Sprache

$L=\{vv^{R}|v\in \Sigma ^{*}\}$

(die Menge der endlichen Wörter gerader Wortlänge, welche Palindrom sind) ist nicht regulär, d.h. man kann keinen regulären Ausdruck angeben, welcher $L$ spezifiziert, bzw. kein endlicher Automat (also eine Maschine mit endlichem Speicher) schafft es $L$ zu erkennen (zu entscheiden, ob ein Wort zur Sprache gehört, oder nicht).

Da beliebig lange, wenn auch endliche, Wörter untersucht werden müssen, ist dafür potentiell unendlich viel Speicher nötig. Man kann zeigen, dass ein Kellerautomat zur Erkennung ausreicht, z. B. indem man konkret eine kontextfreie Grammatik angibt.

Definition (induktiv)

1. Das leere Wort $\epsilon$ (das Wort der Länge 0, der „Leerstring“) ist ein Palindrom.
2. Ist $a$ ein Zeichen, so ist das Wort $a$ ein Palindrom. (Ein Zeichen und ein Wort der Länge 1, welches nur dieses Zeichen enthält sind technisch gesehen unterschiedliche Objekte)
3. Ist $a$ ein Zeichen und $x$ ein Palindrom, so ist ${\mathit {axa}}$ ein Palindrom.
4. Nichts ist ein Palindrom, außer es folgt aus den obigen drei Regeln.

Kontextfreie Grammatik für Palindrome

Die obige induktive Definition ist der Ausgangspunkt für die Konstruktion einer kontextfreien Grammatik für Palindrome.

So kann man z. B. alle Palindrome über dem Alphabet $\Sigma =\{0,1\}$ (Binärwörter) mit diesen Produktionen ableiten:

$S\to 0\,|\,1\,|\,\epsilon$

$S\to 0S0\,|\,1S1$

D.h. aus dem Startsymbol $S$ kann man sofort die Palindrome $\epsilon$ (leeres Wort), $0$ und $1$ erzeugen. Die restlichen Palindrome erhält man, indem man zunächst symmetrisch in beide Richtungen wächst und dann in einem der erstgenannten Wörter (genauer: Terminale) endet.

Z. B.

$S\Rightarrow 0S0\Rightarrow 01S10\Rightarrow 011S110\Rightarrow 011\epsilon \ 110=011110$

oder

$S\Rightarrow 0S0\Rightarrow 010$.

Es ist zu beachten, dass in der Regel $010$ ein gültiges Binärwort (eine Zeichenkette), aber keine gültige Binärzahl (eine Zahl in Binärdarstellung) ist, weil dort führende $0$ Zeichen nicht erlaubt sind ($010$ müsste auf $10$ reduziert werden).

Literatur

• Hopcroft, John E. und Ullman, Jeffrey D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. ISBN 0-201-02988-X (die alte Version, mit mehr Anspruch)
• Stengel, Hansgeorg: AnnasusannA, Berlin, 2004. ISBN 3359014847

Siehe auch

• Palindromische Sequenz – Palindrome in der Genetik
• Kaibun – japanische Satzpalindrome
• Lateinische Palindrome im lateinischen Wiktionary
• Anagramm

Weblinks

Wiktionary: Palindrom – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• Institut für Palindromistik und Senfkunde
• Liste mit Palindromen
• Das längste Palindrom (englisch)
• A Palindrome: Conscious Living Creatures as Instruments of Nature; Nature as an Instrument of Conscious Living Creatures (englisch, Pdf-Datei)