Saturday, 12 March 2011





L-system structure



    G = (V, ω, P),







Examples of L-systems

Example 1: Algae

Lindenmayer's original L-system for modelling the growth of algae.

    variables : A B
    constants : none
    start  : A

which produces:

    n = 0 : A
    n = 1 : AB
    n = 2 : ABA
    n = 3 : ABAAB
    n = 4 : ABAABABA

 Example 1: Algae, explained

n=0:         A           start (axiom/initiator)
            / \
          /|    \
        /| |     |\
      /| | |\    |\ \

 Example 2: Fibonacci numbers

If we define the following simple grammar:

    variables : A B
    constants : none
    start  : A
    rules  : (A → B), (B → AB)

then this L-system produces the following sequence of strings:

    n = 0 : A
    n = 1 : B
    n = 2 : AB
    n = 3 : BAB
    n = 4 : ABBAB
    n = 5 : BABABBAB

These are the mirror images of the strings from the first example, with A and B interchanged. Once again, each string is the concatenation of the preceding two, but in the reversed order.

In either example, if we count the length of each string, we obtain the famous Fibonacci sequence of numbers:


For n>0, if we count the kth position from the invariant end of the string (left in Example 1 or right in Example 2), the value is determined by whether a multiple of the golden mean falls within the interval (k-1,k). The ratio of A to B likewise converges to the golden mean.

This example yields the same result (in terms of the length of each string, not the sequence of As and Bs) if the rule (B → AB) is replaced with (B → BA).

This sequence is a locally catenative sequence because G(n) = G(n-2)G(n-1) where G(n) is the nth generation.
 Example 3: Cantor dust
Cantor set in seven iterations.svg

    variables : A B
    constants : none
    start  : A {starting character string}


 Example 4: Koch curve

A variant of the Koch curve which uses only right-angles.

    variables : F
    constants : + −
    start  : F

Here, F means "draw forward", + means "turn left 90°", and - means "turn right 90°" (see turtle graphics).

    n = 0: Koch Square - 0 iterations


    n = 1: Koch Square - 1 iterations


    n = 2: Koch Square - 2 iterations


    n = 3: Koch Square - 3 iterations

        F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

 Example 5: Penrose tilings



 Example 6: Sierpinski triangle

The Sierpinski triangle drawn using an L-system.

    variables : A B
    constants : + −
    start  : A
    angle  : 60°

Here, A and B both mean "draw forward", + means "turn left by angle", and − means "turn right by angle" (see turtle graphics). The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (they would be in the top and bottom, alternatively, otherwise).
Serpinski Lsystem.svg



    variables : F G
    constants : + −
    start  : F−G−G
    angle  : 120°

 Example 7: Dragon curve

The dragon curve drawn using an L-system.

    variables : X Y
    constants : F + −
    start  : FX
    rules  : (X → X+YF), (Y → FX-Y)
    angle  : 90°

Dragon curve L-system.svg

Dragon curve for n = 10
 Example 8: Fractal plant

    variables : X F
    constants : + −
    start  : X
    angle  : 25°


Fractal plant for n = 6
 Example 9: Modified Koch L-system

A fractal figure drawn introducing a periodic change of angle sign in the iteration of the usual Koch curve L-system.

Open problems



    * Given a structure, find an L-system that can produce that structure.

Types of L-systems

L-systems on the real line R:

    * Prouhet-Thue-Morse system

Well-known L-systems on a plane R2 are:

    * space-filling curves (Hilbert curve, Peano's curves, Dekking's church, kolams),
    * median space-filling curves (Lévy C curve, Harter-Heighway dragon curve, Davis-Knuth terdragon),
    * tilings (sphinx tiling, Penrose tiling),
    * trees, plants, and the like.


    * Przemyslaw Prusinkiewicz, Aristid Lindenmayer - The Algorithmic Beauty of Plants PDF version available here for free
    * Grzegorz Rozenberg, Arto Salomaa - Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology ISBN 978-3-540-55320-5