L-Systeme

Die Theorie der L-Systeme hat ihren Ursprung in Arbeiten von A. Lindenmayer, die in den 60er Jahren über mathematische Modellierung von (biologischen) Entwicklungsprozessen entstanden sind. Inzwischen ist diese Theorie zu einem wichtigen Gebiet der Theorie der formalen Sprachen geworden, das allerdings in den Lehrbüchern noch nicht die entsprechende Berücksichtigung gefunden hat.

Hier soll ein Einstieg in die Theorie der L-Systeme erarbeitet werden. Dazu werden wir uns vorwiegend mit den einfachsten L-Systemen, den sogenannten D0L-Systemen, und den von ihnen erzeugten Folgen und Sprachen befassen. Ein wichtiges Ziel dabei wird die Darstellung der Entscheidbarkeit des D0L-Äquivalenzproblems sein.