Vorlesung: Praxis der Funktionalen Programmierung
L-Systeme
Von Bildern zu Wörtern
Wir legen durch die linke untere Ecke einer beliebigen Inflation
des Ammann-Bausteins eine Gerade mit dem Anstieg 1/2,
und schreiben die Folge der Schnitte auf, die diese Gerade erzeugt.
Es gibt 9 (?) veschiedene Schnitt-Typen,
d. h. wir erhalten ein Wort u über einem Alphabet aus neun Buchstaben.
Bei der nächsten Inflation erhalten wir ein anderes (längeres) Wort v.
Es entsteht durch buchstabenweise Ersetzung aus u,
und außerdem ist u ein Präfix von v.
Im Limes ergibt sich ein unendliches Wort.
(Buchstabenweises Ersetzen heißt vornehm Homomorphismus.)
Der Abstand zwischen zwei Schnittpunkt beträgt sqrt(5)/2 oder sqrt(5).
Nennen wir diese Strecken x und y, dann ist die Folge der
Schnittlängen ein unendliches Wort über dem Alphabet {x, y}.
Es ensteht wiederum durch buchstabenweises Ersetzen
(also einen Homomorphismus) aus dem vorigen Wort.
Lindenmayer
Die Idee der Invarianz unter Inflation (d. h. Selbstähnlichkeit)
gibt es schon lange, und in verschiedensten Bereichen
(der Natur, der Mathematik, der Informatik).
In der Theorie der Formalen Sprachen untersucht man
(seit ca. 100 Jahren!) die später nach Aristid Lindenmayer benannten
System von iterierten Morphismen.
Ein D0L-System ist ein (Endo-)Morphismus und ein Startbuchstabe,
beispielsweise (f, 0) mit
Hier ist 0 echter Präfix von f(0), deswegen ist lim f^n(0)
wohldefiniert (und heißt Fibonacci-Wort) (warum wohl?)
Ein anderer beliebter Morphismus ist
der erzeugt das Thue-Wort. Der folgende schließlich
ergibt das Wort von Morse.
D0L-Implementierung
Wie programmieren wir sowas? Wir benutzen furchtlos unendliche Listen.
Das geht, wegen lazy evaluation: wir dürfen natürlich immer nur
endliche Präfixe ausgeben, und die werden dann auch nur soweit wie nötig
berechnet.
Wir setzen voraus, daß f(0) mit 0 beginnt, also f(0) = 0 : rest.
Dann gilt f^2(0) = f(f(0)) = f(0 : rest) = f(0) ++ f(rest)
= 0 : rest ++ f(rest),
und f^3(0) = 0 : rest ++ f(rest) ++ f(f(rest)), und so weiter.
Das unendliche Wort w nach der 0 hat also die Eigenschaft
w = rest ++ f (w), und genau das nehmen wir als Programm
(siehe Quelltext).
Muster
Auf solche Wörter stieß man bei der Frage danach,
ob es beliebig lange Folgen von Buchstaben gibt,
die kein Quadrat, also ein Teilwort der Form uu, enthalten;
bzw. keine dritte Potenz. Das Thue-Wort ist kubikfrei,
das Morse-Wort ist quadratfrei.
Im noch Allgemeineren kann man nach Teilwörtern wie xxyxy fragen
(alle x sind durch dasselbe Wort zu ersetzen, usw.)
HD0L
Ein HD0L-System ist ein D0L-System (f,x) und ein weiterer Morphismus h.
Es erzeugt ein unendliches Wort, indem man auf das D0L-Wort lim f^n(x)
schließlich den Morphismus h anwendet.
Beispiel: wir nehmen das Morse-Wort und den Morphismus
Fragen zu (H)D0L-Systemen
(stehen auch im Quelltext)
- Entscheide, ob ein gegebenes (H)D0L-System ein gegebenes Muster vermeidet
- Entscheide, ob ein gegebenes Muster durch irgendein (H)D0L-System
vermeidbar ist
- Entscheide, ob zwei gegebene HD0L-Systeme das gleiche unendliche Wort
erzeugen
Ich plane für das nächste Semester ein Seminar über Morphismen und L-Systeme,
wo wir diesen Fragen auf den Grund gehen können.
Die Dinge sind sehr interessant, aber auch recht schwer,
und viele Fragen sind offen. Trotzdem kann man durch mutiges Probieren
sicher etwas erreichen, zum Beispiel ein Diplom.
Die Versuche dazu können bereits jetzt beginnen.
Literatur
http://www.informatik.uni-leipzig.de/~joe/
mailto:joe@informatik.uni-leipzig.de