Palindrom

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Dieser Artikel beschäftigt sich mit dem Worttyp „Palindrom“. Für eine Beschreibung des gleichnamigen Films siehe Palindrome.

Ein Palindrom (v. griech.: Παλίνδρομος (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. Das Palindrom ist eine spezielle Form des Anagramms.

Darüber hinaus werden auch Wörter, 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.

Inhaltsverzeichnis

1 Beispiele
- 1.1 von vorn und hinten gelesen gleichlautend
- 1.2 rückwärts gelesen sinnvoll
2 Palindrome in der Informatik
3 Literatur
4 Siehe auch
5 Weblinks

Beispiele

von vorn und hinten gelesen gleichlautend

Wortpalindrome

Hauptliste: Liste von Wortpalindromen

Anna
Rentner
Reittier
Lagerregal / Regallager
Reliefpfeiler
Saippuakivikauppias (längstes Palindrom, finnisch)

Otto, Reittier 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.
Erika feuert nur untreue Fakire.
Nie, Amalia, lad' 'nen Dalai Lama ein.
Der Freibier-Fred.
Ein Neger mit Gazelle zagt im Regen nie.

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 = GNUDUNG

zerlegen mit

v = GNU

und

c = 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 = \{ v v^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)

Das leere Wort $ε$ (das Wort der Länge 0, der „Leerstring“) ist ein Palindrom.
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)
Ist $a$ ein Zeichen und $x$ ein Palindrom, so ist $a x a$ ein Palindrom.
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 $Σ = {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 $ε$ (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