Palindrom

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel beschäftigt sich mit dem Worttyp „Palindrom“; zur Beschreibung des gleichnamigen Films siehe Palindrome.

Ein Palindrom (von griechisch Παλίνδρομος (palíndromos) „rückwärts laufend“) ist eine Zeichenkette, die von vorn und von hinten gelesen gleich bleibt. Palindrome müssen nicht immer einen Sinn ergeben, die Zeichenkette muss allerdings von vorne nach hinten und von hinten nach vorne bezüglich der Reihenfolge der verwendeten Zeichen übereinstimmen.

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).[1][2][3] In diesem weiteren Sinne ist das Palindrom eine spezielle Form des Anagramms. Verwandt zum Palindrom ist das Ambigramm, bei dem sich meist nach einer 180°-Drehung noch dasselbe Wort ergibt.

Laut Guinness-Buch der Rekorde von 1997 lautet das längste deutsche Ein-Wort-Palindrom Reliefpfeiler (dt. für Pilaster). Dieses Wortpalindrom besitzt als kunstgeschichtlicher Terminus keine besondere Bedeutung. Das Kompositum gilt aber als ein bemerkenswertes Palindrom, weil ein langes Palindrom in der deutschen Sprache selten ist. Das Kompositum wird als Beispiel bereits in Meyers Großes Konversations-Lexikon von 1905 erwähnt.[4] Seine „Entdeckung“ wird häufig dem Philosophen Arthur Schopenhauer zugeschrieben – eine Behauptung, die näherer Überprüfung allerdings nicht standhält.[5] Länger als Reliefpfeiler ist jedoch das Wort Retsinakanister. 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 Datumspalindrome, z. B. der 10.02.2001, und Zeitpalindrome, z. B. 13:31.

In der Genetik spielen palindromische Sequenzen eine Rolle für die Konformation der DNA.

Inhaltsverzeichnis

Beispiele

Wortpalindrome

Siehe auch: Deutsche Wortpalindrome.

Otto, Reittier und Rotor sind zusätzlich Morsecode-Palindrome, da sie ausschließlich aus symmetrischen Morsezeichen bestehen. Es existieren Morsecodepalindrome, die in lateinischen Buchstaben keine Palindrome mehr sind, wie zum Beispiel du (— · ·, · · —), an (· —, — ·) oder je (· — — —, ·).

Satzpalindrome

Siehe auch: Deutsche Satzpalindrome.

rückwärts gelesen sinnvoll

Sonstiges

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 über dem Alphabet Σ mit der Eigenschaft

u = uR,

wobei uR bedeutet, dass der Operator R der Spiegelung (bzw. Umkehrung der Reihenfolge der Zeichen) auf das Wort u angewandt wird. Zu beachten ist, 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. keinen endlichen Automaten (also eine Maschine mit endlichem Speicher), der es schafft, L zu erkennen (d.h. zu entscheiden, ob ein Wort zur Sprache L gehört oder nicht).

Da beliebig lange, wenn auch endliche, Wörter untersucht werden müssen, ist potentiell unbeschränkt viel Speicher nötig, um sich v zu merken und dann anschließend mit vR zu vergleichen. Man kann zeigen, dass ein nichtdeterministischer Kellerautomat zur Erkennung ausreicht, z.B. indem man konkret eine kontextfreie Grammatik angibt. Jedoch gibt es keinen deterministischen Kellerautomaten, der diese Sprache erkennt.

Rekursive Definition

Die induktive bzw. rekursive Definition für Palindrome sieht wie folgt aus:

  1. Das leere Wort ε (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 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.

Zuerst wird eine intuitiv verständliche Produktion für Palindrome vorgestellt. Diese genügt aber rein formell nicht den Ansprüchen einer kontextfreien Grammatik in der Normalform. Weiter unten wird eine formell korrekte kontextfreie Grammatik für Palindrome vorgestellt.

Vereinfachte anormale Produktion

Vereinfacht 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).

Normalform

Eine formell korrekte Produktion einer kontextfreien Grammatik in Normalform kennt keine Regel, bei der das Startsymbol reproduziert wird, wenn dies gleichzeitig einen Übergang zu einem leeren Wort ermöglicht. Diese Einschränkung erfordert hier den Übergang in einen weiteren Zustand A, von dem aus weiterproduziert wird.

Eine weitere Definition einer kontextfreien Grammatik für die Erzeugung von Palindromen über dem Alphabet Σ = {0,1} lautet also:

G = ({S,A},{0,1},P,S)

mit den Produktionsregeln P:

S \to 0\,|\,1\,|\,00\,|\,11\,|\,\epsilon
S \to 0A0\,|\,1A1
A \to 0A0\,|\,1A1
A \to 0\,|\,1\,|\,00\,|\,11

Die erzeugte Sprache ist mit der obigen identisch.

Z. B.

S \Rightarrow 0A0 \Rightarrow 01A10 = 011110

oder

S \Rightarrow 0A0 = 010

Einzelnachweise und Fußnoten

  1. ↑ Duden - Deutsches Universalwörterbuch, 6. Auflage
  2. ↑ Der Brockhaus in einem Band, 2008
  3. ↑ Lexikon des Wissen Media Verlag sowie Wahrig Rechtschreibung und Bertelsmann Wörterbuch
  4. ↑ online unter http://zeno.org/Meyers-1905/A/Palindr%C5%8Dm
  5. ↑ vgl. die Nachforschungen im Blogeintrag Schopenhauer und die Palindrome unter http://blog.trauerfreuart.de/2008/05/schopenhauer-und-die-palindrome.html, abgerufen am 21. Februar 2009
  6. ↑ http://www.thomkins.com/ www.thomkins.com
  7. ↑ http://blog.trauerfreuart.de/2007/12/andre-thomkins-palindrome-auf.html Andre-Thomkins-Palindrome

Literatur

Siehe auch

Weblinks

Von „http://de.wikipedia.org/wiki/Palindrom“
Meine Werkzeuge
Namensräume
Varianten
Aktionen
Navigation
Mitmachen
Drucken/exportieren
Werkzeuge
In anderen Sprachen