Palindrom

Palindrome (v. griech.: Παλίνδρομος (palíndromos) = rückwärts laufend) sind Zeichenketten, die von vorn und hinten gelesen gleich bleiben (wie zum Beispiel das Wort Rentner). Sie 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. Das Palindrom ist eine spezielle Form des Anagramms.

Darüber hinaus werden auch Worte, Wortreihen oder Sätze als Palindrome bezeichnet, die rückwärts gelesen einen Sinn haben (wie zum Beispiel die Worte Lager – Regal).

Laut Guinnessbuch der Rekorde von 1997 lautet das längste deutsche Ein-Wort-Palindrom Reliefpfeiler, wobei jedoch das Wort Retsinakanister noch länger ist. Eine verwandte Form des Palindroms ist das Ambigramm, bei dem sich meist nach einer 180°-Drehung noch dasselbe Wort ergibt.

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.

Die Angst vor Palindromen nennt man phantasievoll „Eibohphobie“, was ebenso ein Palindrom darstellt.

Beispiele

von vorn und hinten gelesen gleichlautend

Wortpalindrome

Hauptliste: Liste von Wortpalindromen

• Anna
• Rentner
• Reittier
• Lagerregal / Regallager
• Reliefpfeiler

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

Satzpalindrome

Hauptliste: Liste von Satzpalindromen

• Nie solo sein
• Madam, I'm Adam.
• O Genie, der Herr ehre Dein Ego!
• Eine güldne, gute Tugend: Lüge nie!
• O renne, bei drei Papierdieben, Nero!
• Die Liebe ist Sieger; stets rege ist sie bei Leid.

Zahlenpalindrome

Die Dezimalzahl 5141 ist das Palindrom ihrer Hexadezimaldarstellung:

$5141_{(10)}=1415_{(16)}$.

rückwärts gelesen sinnvoll

• Ein – Nie
• Eber – Rebe
• Nebel – Leben
• Sarg – Gras
• Lager - Regal

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, ausser 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

Weblinks

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

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