L-system

An L-system or Lindenmayer system is a formal grammar (a set of rules and symbols) most famously used to model the growth processes of plant development, though able to model the morphology of a variety of organisms. L-systems can also be used to generate self-similar fractals such as iterated function systems. L-systems were introduced and developed in 1968 by the Hungarian theoretical biologist and botanist from the University of Utrecht, Aristid Lindenmayer (1925-1989).

Contents
1 Origins
2 L-system structure
3 Examples of L-systems

3.1 Example 1: Algae
3.2 Example 2: Fibonacci numbers
3.3 Example 3: Cantor dust
3.4 Example 4: Koch curve
3.5 Example 5: Penrose tilings

4 Open problems
5 Types of L-systems
6 External links

Origins

Missing image
Fractal_weeds.jpg
'Weeds', generated from a L-system in three dimensions.

As a biologist, Lindenmayer worked with yeast and filamentous fungi and studied the growth patterns of various types of algae, such as the blue-green bacteria Anabaena catenula. Originally the L-systems were devised to provide a formal description of the development of such simple multicellular organisms, and to illustrate the neighbourhood relationships between plant cells. Later on, this system was extended to describe higher plants and complex branching structures.

L-system structure

The recursive nature of the L-system rules leads to self-similarity and thereby fractal-like forms are easy to describe with an L-system. Plant models and naturally-looking organic forms are similarly easy to define, as by increasing the recursion level the form slowly 'grows' and becomes more complex. Lindenmayer systems are also popular in the generation of artificial life.

L-system grammars are very similar to the semi-Thue grammar (see Chomsky hierarchy). L-systems are now commonly known as parametric L systems, defined as a set

G = {V, S, ω, P},

where

The rules of the L-system grammar are applied iteratively starting from the initial state.

An L-systems is context-free if each production rule refers only to an individual symbol and not to its neighbours. If a rule depends not only on a single symbol but also on its neighbours, it is termed a context-sensitive L-system.

If there is exactly one production for each symbol, then the L-system is said to be deterministic (a deterministic context-free L-system is popularly called a D0L-system). If there are several, and each is chosen with a certain probability during each iteration, then it is a stochastic L-system.

Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen. For example, the program FractInt (see external links below) uses turtle graphics (similar to those in the Logo programming language) to produce screen images. It interprets each constant in an L-system model as a turtle command (see turtle graphics).

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
rules  : (A → AB), (B → A)

which produces:

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

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
n=6 : ABBABBABABBAB
n=7 : BABABBABABBABBABABBAB

and if we count the length of each string, we obtain the famous Fibonacci sequence of numbers:

1 1 2 3 5 8 13 21 34 55 89 ...

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

Example 3: Cantor dust

variables : A B
constants : none
start  : A {starting character string}
rules  : (A → ABA), (B → BBB)

Let A mean "draw forward" and B mean "move forward".

This produces the famous Cantor's fractal set on a real straight line R.

Example 4: Koch curve

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

variables : F
constants : + −
start  : F
rules  : (F → F+F−F−F+F)

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

n=0: Missing image
Square_koch_0.png
Koch Square - 0 iterations

           F
n=1: Missing image
Square_koch_1.png
Koch Square - 1 iterations

           F+F-F-F+F
n=2: Missing image
Square_koch_2.png
Koch Square - 2 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
n=3: Missing image
Square_koch_3.png
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

The following images were generated by an L-system. They are related and very similar to Penrose tilings, invented by Roger Penrose. 

    Missing image
Penam01c.gif
image:penam01c.gif

  
     Missing image
Penam02c.gif
image:penam02c.gif

As an L-system these tilings are called Penrose's rhombuses and Penrose's tiles. The above pictures were generated for n=6 as an L-system. If we properly superimpose Penrose tiles as an L-system we get next tiling: 

    Missing image
Pend05c.gif
image:pend05c.gif

otherwise we get patterns which do not cover an infinite surface completely: 

    Missing image
Pendx05c.gif
image:pendx05c.gif

Open problems

There are many open problems involving studies of L-systems. For example:

Types of L-systems

L-systems on a real straight line R:

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

External links

See also: L-system, 1925, 1968, 1989, Aristid Lindenmayer, Artificial life, Biologist, Botanist, Cantor dust, Chomsky hierarchy