L-system

An L-system or Lindenmayer system is a set of rules and symbols (a formal grammar) very similar to a semi-Thue grammar[?] (see Chomsky hierarchy). It may be used to model the growth processes of plant development, the morphology of a variety of organisms introduced and developed in 1968 by the Swedish theoretical biologist and botanist from the University of Utrecht[?], Aristid Lindenmayer (1925-1989). He worked with yeast and filamentous fungi[?] and studied the growth patterns of a type of algae, a simple multicellular organisms, such as blue-green bacteria Anabaena catenula[?]. Originally the L-systems were devised to provide a formal description of the development of 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.

Lindenmayer systems are also popular in the generation of artificial life.

An L-system provides mathematical formalisms to describe the growth of simple and even complex plants. Lindenmayer Systems are very often self-similar and thereby fractals.

An L-system is a rule-like description of a 2D or 3D form. It contains descriptions of parts and how they should be assembled together. The description is applied to itself a number of times (e.g., recursion levels) so fractal and recursive forms are very easy to describe in an L-system. This is why they are used a lot for plants and naturally-looking organic forms. By increasing the recursion level, the form slowly 'grows' and becomes more complex. L-systems are now commonly known as parametric L systems, defined as a set G = {V, S, ω, P}. Such simple parametric L-systems contain four elements:

• variables or an alphabet - symbols denoting elements that can are replaced
• constants - symbols denoting elements that remain fixed
• start, axiom or initiator - an expression defining the initial state of the system
• rules ("syntax") or productions - expressions defining the way variables are replaced with combinations of constants and other variables. A production consists of two strings - the predecessor and the successor.

Table of contents 1 Examples 2 Open problems 3 Types of L-systems 3.1 External links

Examples

Example 1: Original Lindenmayer L-system for his algae:

variables : A

constants : none

start : A

rules : (A → AB), (B → A)

what produces:

n=0 : A → AB

n=1 : AB → ABA

n=2 : ABA → ABAAB

n=3 : ABAAB → ABAABABA

Example 2: Fibonacci numbers. If we define a simple grammar, defined by:

variables : A B

constants : none

start : A

rules : (A → B), (B → AB)

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 : ø 6 {set angle increment to (360/6)=60 degrees}

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: A variant of the Koch snowflake which uses only right-angles:

variables : F

constants : none

start : F

rules : (F → F+F-F-F+F)

Here, F means "draw forward", + is "turn left 90°", and - is "turn right 90°".

n=0:

            F

n=1:

            F+F-F-F+F

n=2:

            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:

            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

...

A Lindenmayer system consists of a start symbol, a set of production rules and some definitions of the meaning of the symbols. 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.

An L-systems is context-free if each production rule (like in the above examples) 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. If there are several, and each is chosen with a certain probability during each iteration, then it is a stochastic L-system.

A deterministic context-free L-system is popularly called a D0L-system.

Open problems

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

• Characterisation of all the deterministic context-free L-systems which are locally catenative. (A complete solution is known only in the case where variables are only two).

Types of L-systems

L-systems on a real straight line R:

• Prouhet-Thue-Morse system[?]

Another well known L-system on a plane R² are:

• spacefilling curves (Hilbert's curve[?], Peano's curves[?], Dekking's church, kolams[?]),
• median spacefilling curves (Levy dragon curve[?], Harter-Heighway dragon curve, Davis-Knuth terdragon),
• tilings (Sphinx tiling, Penrose tiling),
• trees, plants and similar.

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

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:

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

External links

• Good Wright's article on L-systems (http://www.math.okstate.edu/mathdept/dynamics/lecnotes/node12#SECTION00040000000000000000)
• Fractint L-System True Fractals (http://spanky.triumf.ca/www/fractint/lsys/truefractal)
• Fractint home page (http://spanky.triumf.ca/www/fractint/fractint)