Palimdron mit Wörtern

04.11.2008, 23:33

prinzschleifer

Palimdron mit Wörtern

Also mal wieder eine Aufgabe für die Informatiker:

Es sei A ein Alphabet. Die Abbildung $\begin{eqnarray*} F: A^* -> A^* \end{eqnarray*}$ sei wie folgt definiert.
$\begin{eqnarray*} F( \varepsilon ) = \varepsilon \end{eqnarray*}$
$\begin{eqnarray*} \forall w \in A^* \forall x \in A: F(xw) = F(w)x \end{eqnarray*}$

Man soll R(abbab) berechnen.

Lieg ich richtig in der Annahme, dass sich einfach die Reihenfolge ändert?
Also R(abbab) = babba

Fernen soll man bestimmen für wieviele Wörter w der Länge n für $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ F(w)=w gilt.

Auf Deutsch also, wenn es sich um ein Palindrom handelt. Ich habe bereits probiert und bin darauf gekommen, dass es ein unterschied macht ob es eine gerade oder eine ungerade Zahl n ist.

Nun verlier ich einfach nach 7 den Überblick. Hier mal eine Liste, bei der ich aber nicht weiß ob sie vollständig ist. Ich habe bereits einen guten Zusammenhang für Palindrome gefunden:

Ein Palindrom ist ein Wort, bei dem Anfangs- und Endbuchstabe identisch sind und das dazwischen verbleibende Wort ein Palindrom
ist oder h¨ochstens einen Buchstaben besitzt.

Leider hilft mir das nur weiter wenn ich das via eines Programms rekursiv überprüfen will. In der Aufgabe steht leider nicht für welches Alphabet, deswegen nehm ich erstmal $\begin{eqnarray*} A=\left\{ a,b \right\} \end{eqnarray*}$ an.

Zusammenhänge, die ich bereits festgestellt habe:

für |w|=n=3 und für die gilt F(w)=w -> 4

für |w|=n=5 und für die gilt F(w)=w

abbba
aabaa
aaaaa
baaab
bbabb
bbbbb
babab
ababa
...

für |w|=n=7 und für die gilt F(w)=w

aaaaaaa
bbbbbbb
abbbbba
aabbbaa
aaabaaa
baaaaab
bbaaabb
bbbabbb
bbbabbb
abbabba
bababab
aababaa
...

Gibt es irgendeine Formel für sowas? Mir fällt grade keine ein. Vielleicht die palimdromische Fakultät?

Vielen dank für irgendeinen Lösungsansatz!

05.11.2008, 00:39

papahuhn

Auf diesen Beitrag antworten »

RE: Palimdron mit Wörtern

Zitat:

Original von prinzschleifer
Fernen soll man bestimmen für wieviele Wörter w der Länge n für $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ F(w)=w gilt.

Auf Deutsch also, wenn es sich um ein Palindrom handelt.

Mit oder ohne Beweis?
Der Standardweg wäre der:
1. Menge der Palindrome induktiv definieren.
2. Zeigen, dass Palindrome unter F fix bleiben.
3. Induktive Definition nutzen, um eine rekursive Formel für die Anzahl der Palindrome fixer Länge zu erhalten.
4. Rekursive Formel zu einer direkten umwandeln.

05.11.2008, 00:42

prinzschleifer

Auf diesen Beitrag antworten »

Ohne Beweis!

So nun geh ich ins Bettchen und grübel darüber nach.

Gibt es da keinen anschaulichen Weg?

05.11.2008, 01:00

papahuhn

Auf diesen Beitrag antworten »

Dann ist der Weg der gleiche, bloß dass du die einzelnen Punkte nicht beweisen musst. Die Struktur hast du ja selbst bereits erkannt:

Zitat:

Ein Palindrom ist ein Wort, bei dem Anfangs- und Endbuchstabe identisch sind und das dazwischen verbleibende Wort ein Palindrom ist oder höchstens einen Buchstaben besitzt.

.

Einbuchstabige Wörter sind übrigens auch Palindrome, ebenso das leere Wort.
Nun suchen wir eine Funktion f mit $\begin{eqnarray*} f(n) = \text{Anzahl der Palindrome der Länge n} \end{eqnarray*}$ .

Dazu nutzen wir strukturelle Induktion:
$\begin{eqnarray*} f(0) = 1 \end{eqnarray*}$ , denn es gibt nur ein Palindrom der Länge 0, das leere Wort.
$\begin{eqnarray*} f(1) = |A| \end{eqnarray*}$ , denn jeder Buchstabe ist ein Palindrom.
$\begin{eqnarray*} f(n) = |A|*f(n-2) \end{eqnarray*}$ , denn ein Palindrom hat sonst die Form xvx, mit beliebigen $\begin{eqnarray*} x \in A \end{eqnarray*}$ und Palindromen v. v hat natürlich Länge n-2, und deren Anzahl kennen wir ja bereits, nach IV.

Neue Frage »

Antworten »

Palimdron mit Wörtern

Verwandte Themen