An Lsystem 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. Lsystems were introduced and developed in 1968 by the Hungarian theoretical biologist and botanist from the University of Utrecht, Aristid Lindenmayer (19251989).
Origins
As a biologist, Lindenmayer worked with yeast and filamentous fungi and studied the growth patterns of various types of algae, such as the bluegreen bacteria Anabaena catenula . Originally the Lsystems 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.
Lsystem structure
The recursive nature of the Lsystem rules leads to selfsimilarity and thereby fractallike forms are easy to describe with an Lsystem. Plant models and naturallylooking 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.
Lsystem grammars are very similar to the semiThue grammar (see Chomsky hierarchy). Lsystems are now commonly known as parametric L systems, defined as a set
 G = {V, S, ω, P},
where
 V (the alphabet) is a set of symbols containing elements that can be replaced (variables)
 S is a set of symbols containing elements that remain fixed (constants)
 ω (start, axiom or initiator) is a string of symbols from V defining the initial state of the system
 P is a set of rules or productions defining the way variables can be replaced with combinations of constants and other variables. A production consists of two strings  the predecessor and the successor.
The rules of the Lsystem grammar are applied iteratively starting from the initial state.
An Lsystems is contextfree 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 contextsensitive Lsystem.
If there is exactly one production for each symbol, then the Lsystem is said to be deterministic (a deterministic contextfree Lsystem is popularly called a D0Lsystem). If there are several, and each is chosen with a certain probability during each iteration, then it is a stochastic Lsystem.
Using Lsystems 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 Lsystem model as a turtle command (see turtle graphics).
Examples of Lsystems
Example 1: Algae
Lindenmayer's original Lsystem 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
If we define the following simple grammar:
 variables : A B
 constants : none
 start : A
 rules : (A → B), (B → AB)
then this Lsystem 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).
 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 rightangles.
 variables : F
 constants : + 
 start : F
 rules : (F → F+FFF+F)
Here, F means "draw forward", + means "turn left 90°", and  means "turn right 90°" (see turtle graphics).

n=0:
F

n=1:
F+FFF+F

n=2:
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F

n=3:
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F+
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F+
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F
Example 5: Penrose tilings
The following images were generated by an Lsystem. They are related and very similar to Penrose tilings, invented by Roger Penrose.
As an Lsystem these tilings are called Penrose's rhombuses and Penrose's tiles. The above pictures were generated for n=6 as an Lsystem. If we properly superimpose Penrose tiles as an Lsystem we get next tiling:
otherwise we get patterns which do not cover an infinite surface completely:
Open problems
There are many open problems involving studies of Lsystems. For example:
 Characterisation of all the deterministic contextfree Lsystems which are locally catenative. (A complete solution is known only in the case where there are only two variables).
Types of Lsystems
Lsystems on a real straight line R:
 ProuhetThueMorse system
Wellknown Lsystems on a plane R^{2} are:
 spacefilling curves (Hilbert's curve , Peano's curves, Dekking's church, kolams),
 median spacefilling curves (Lévy C curve, HarterHeighway dragon curve, DavisKnuth terdragon),
 tilings (Sphinx tiling, Penrose tiling),
 trees, plants and similar.
External links
Last updated: 05162005 08:09:35