Theoretische Informatik

Lindenmayer-Systeme

 aufwärts

Ein Lindenmayer-System oder L-System (nach A. Lindenmayerzur Person) ist, ähnlich wie eine Grammatik, ein Ersetzungs­system zur Beschreibung einer formalen Sprache. Im Unterschied zur Grammatik werden in einem L-System alle anwendbaren Ersetzungs­regeln parallel ausgeführt.

Konzept

Definition:  Ein deterministisches 0L-System (D0L-System) 1) ist ein Tripel

D  =  (A, P, s).

Hierbei ist

A ein Alphabet,
P : A Pfeil nach rechts A* eine Abbildung, die Menge der Produktionen,
s Element A+ das Startwort.

Die Produktionen eines D0L-Systems ordnen also jedem Zeichen des Alphabets ein Wort zu. Ähnlich wie bei einer Grammatik werden die Produktionen als Ersetzungs­regeln aufgefasst: Jedes Zeichen a Element A lässt sich durch das Wort P(a) = w ersetzen; wir schreiben daher auch a Pfeil nach rechts w.

Schreibweise:  Bei D0L-Systemen geben wir Produktionen der Form a Pfeil nach rechts a nicht explizit an. Wenn also für ein Alphabet­zeichen a keine Produktion angeben ist, so gilt a Pfeil nach rechts a.

Die Abbildung P lässt sich in natürlicher Weise auf ganze Wörter erweitern. Sie wird dadurch zu einem Halbgruppen-Homo­morphismus P : APfeil nach rechts A*.

Definition:  Sei x = x0 ... xn-1 ein Wort über A. Die Erweiterung der Abbildung P auf das Wort x ergibt sich als

P(x0 ... xn-1)   =   P(x0) ... P(xn-1)

Die Produktionen werden also auf alle Zeichen des Wortes x parallel angewandt. Aus dem Wort x entsteht so ein neues Wort P(x) = y; wir schreiben in diesem Fall auch x Pfeil nach rechts y.

Auf das neue Wort y kann nun wieder P angewandt werden, usw. Auf diese Weise werden fortgesetzt neue Wörter erzeugt. Die Menge aller dieser Wörter bildet die von dem D0L-System erzeugte Sprache.

Definition:  Sei D  =  (A, P, s) ein D0L-System. Die von D erzeugte Sprache ist

L(D)  =  { w  |  s grammatikalische Ableitung w },

also die Menge aller Wörter, die durch parallele Anwendung der Produktionen in 0, einem oder mehreren Schritten aus dem Startwort erzeugt werden können. Ein solcher Schritt wird auch als Generation bezeichnet.

Der Unterschied zwischen einem D0L-System und einer kontext­freien Grammatik besteht zum einen darin, dass bei einem D0L-System in einem Ableitungs­schritt alle anwendbaren Produktionen parallel angewendet werden, während bei einer Grammatik in einem Ableitungs­schritt immer nur eine Produktion angewendet wird. Zum anderen wird bei einem D0L-System anders als bei einer Grammatik nicht zwischen Variablen und Terminal­zeichen unter­schieden.

Beispiele

Beispiel:  

  1. Das D0L-System

    D   =   ( {a}, {a Pfeil nach rechts aa}, a )

    erzeugt die Sprache

    L(D)   =   { a2n | n Element natürliche Zahlen0 }   =   { a, aa, aaaa, aaaaaaaa, ... }.

    Die Längen der Wörter entsprechen den Zweier­potenzen.

    Im ersten Ableitungs­schritt wird das Zeichen a im Startwort gemäß der Produktion a Pfeil nach rechts aa durch aa ersetzt. Im zweiten Ableitungs­schritt werden in dem Wort aa alle vorkommenden a's parallel durch aa ersetzt, das Ergebnis ist aaaa, usw.

     

  2. Das D0L-System

    D   =   ( {a, b}, {a Pfeil nach rechts b, b Pfeil nach rechts ab }, a )

    erzeugt die Sprache

    L(D)   =   { a, b, ab, bab, abbab, bababbab, ... }.

    Ab dem dritten Wort ergibt sich jedes Wort als Verkettung der beiden vorherigen Wörter. Die Längen der Wörter entsprechen den Fibonacci-Zahlen.

     

    In folgendem Beispiel ist gemäß der oben vereinbarten Schreibweise die Produktion c Pfeil nach rechts c nicht explizit angegeben:

  3. Das D0L-System

    D   =   ( {a, b, c}, {a Pfeil nach rechts abcc, b Pfeil nach rechts bcc }, a )

    erzeugt die Sprache

    L(D)   =   { a, abcc, abccbcccc, abccbccccbcccccc, ... }.

    Die Längen der Wörter entsprechen den Quadrat­zahlen.

Die Beispiele zeigen zunächst, dass mit L-Systemen unter­schiedliche Wachstums­funktionen realisiert werden können. In der Praxis werden L-Systeme vorwiegend zur Erzeugung von geo­metrischen Objekten verwendet. Hierbei werden die Alphabet­zeichen als bestimmte geometrische Operationen inter­pretiert.

Literatur

[Sal 73]A.K. Salomaa: Formal Languages. Academic Press (1973)

1)  In der Bezeichnung 0L-System steht die 0 (Null) für kontextfrei (Null Kontext). Die Aussprache ist aber "Oh-El-System".

 

Weiter mit:   [Raumfüllende Kurven]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 20.12.2012   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik