L-system


An L-system or Lindenmayer system is a rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial "axiom" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures. L-systems were introduced and developed in 1968 by Aristid Lindenmayer, a Hungarian theoretical biologist and botanist at the University of Utrecht. Lindenmayer used L-systems to describe the behaviour of plant cells and to model the growth processes of plant development. L-systems have also been used to model the morphology of a variety of organisms and can be used to generate self-similar fractals.

Origins

As a biologist, Lindenmayer worked with yeast and filamentous fungi and studied the growth patterns of various types of bacteria, such as the cyanobacteria 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 natural-looking organic forms are 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. L-systems are now commonly known as parametric L systems, defined as a tuple
where
The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration. The fact that each iteration employs as many rules as possible differentiates an L-system from a formal language generated by a formal grammar, which applies only one rule per iteration. If the production rules were to be applied only one at a time, one would quite simply generate a language, rather than an L-system. Thus, L-systems are strict subsets of languages.
An L-system is context-free if each production rule refers only to an individual symbol and not to its neighbours. Context-free L-systems are thus specified by a context-free grammar. 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.
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 uses turtle graphics to produce screen images. It interprets each constant in an L-system model as a turtle command.

Examples of L-systems

Example 1: Algae

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

Example 1: Algae, explained

n=0: A start
/ \
n=1: A B the initial single A spawned into AB by rule, rule couldn't be applied
/| \
n=2: A B A former string AB with all rules applied, A spawned into AB again, former B turned into A
/ | | | \
n=3: A B A A B note all A's producing a copy of themselves in the first place, then a B, which turns...
/ | | | \ | \ \
n=4: A B A A B A B A ... into an A one generation later, starting to spawn/repeat/recurse then
The result is the sequence of Fibonacci words. If we count the length of each string, we obtain the famous Fibonacci sequence of numbers :
For each string, if we count the k-th position from the left end of the string, the value is determined by whether a multiple of the golden ratio falls within the interval. The ratio of A to B likewise converges to the golden mean.
This example yields the same result if the rule is replaced with, except that the strings are mirrored.
This sequence is a locally catenative sequence because, where is the n-th generation.

Example 2: Fractal (binary) tree

The shape is built by recursively feeding the axiom through the production rules. Each character of the input string is checked against the rule list to determine which character or string to replace it with in the output string. In this example, a '1' in the input string becomes '11' in the output string, while ': pop position and angle, turn right 45 degrees
The push and pop refer to a LIFO stack. When the turtle interpretation encounters a ''. If multiple values have been "pushed," then a "pop" restores the most recently saved values. Applying the graphical rules listed above to the earlier recursion, we get:

Example 3: Cantor set

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.
Here, F means "draw forward", + means "turn left 90°", and − means "turn right 90°".

Example 5: Sierpinski triangle

The Sierpinski triangle drawn using an L-system.
Here, F and G both mean "draw forward", + means "turn left by angle", and − means "turn right by angle".
It is also possible to approximate the Sierpinski triangle using a Sierpiński arrowhead curve L-system.
Here, A and B both mean "draw forward", + means "turn left by angle", and − means "turn right by angle".
Evolution for n = 2, n = 4, n = 6, n = 8

Example 6: Dragon curve

The dragon curve drawn using an L-system.
Here, F means "draw forward", − means "turn left 90°", and + means "turn right 90°". X and Y do not correspond to any drawing action and are only used to control the evolution of the curve.
Dragon curve for n = 10

Example 7: Fractal plant

Here, F means "draw forward", − means "turn left 25°", and + means "turn right 25°". X does not correspond to any drawing action and is used to control the evolution of the curve. The square bracket "" is executed.
Fractal plant for n = 6

Variations

A number of elaborations on this basic L-system technique have been developed which can be used in conjunction with each other. Among these are stochastic grammars, context sensitive grammars, and parametric grammars.

Stochastic grammars

The grammar model we have discussed thus far has been deterministic—that is, given any symbol in the grammar's alphabet, there has been exactly one production rule, which is always chosen, and always performs the same conversion. One alternative is to specify more than one production rule for a symbol, giving each a probability of occurring. For example, in the grammar of Example 2, we could change the rule for rewriting "0" from:
to a probabilistic rule:
Under this production, whenever a "0" is encountered during string rewriting, there would be a 50% chance it would behave as previously described, and a 50% chance it would not change during production. When a stochastic grammar is used in an evolutionary context, it is advisable to incorporate a random seed into the genotype, so that the stochastic properties of the image remain constant between generations.

Context sensitive grammars

A context sensitive production rule looks not only at the symbol it is modifying, but the symbols on the string appearing before and after it. For instance, the production rule:
transforms "a" to "aa", but only If the "a" occurs between a "b" and a "c" in the input string:
As with stochastic productions, there are multiple productions to handle symbols in different contexts. If no production rule can be found for a given context, the identity production is assumed, and the symbol does not change on transformation. If context-sensitive and context-free productions both exist within the same grammar, the context-sensitive production is assumed to take precedence when it is applicable.

Parametric grammars

In a parametric grammar, each symbol in the alphabet has a parameter list associated with it. A symbol coupled with its parameter list is called a module, and a string in a parametric grammar is a series of modules. An example string might be:
The parameters can be used by the drawing functions, and also by the production rules. The production rules can use the parameters in two ways: first, in a conditional statement determining whether the rule will apply, and second, the production rule can modify the actual parameters. For example, look at:
The module a undergoes transformation under this production rule if the conditional x=0 is met. For example, a would undergo transformation, and a would not.
In the transformation portion of the production rule, the parameters as well as entire modules can be affected. In the above example, the module b is added to the string, with initial parameters. Also, the parameters of the already existing module are transformed. Under the above production rule,
Becomes
as the "x" parameter of a is explicitly transformed to a "1" and the "y" parameter of a is incremented by one.
Parametric grammars allow line lengths and branching angles to be determined by the grammar, rather than the turtle interpretation methods. Also, if age is given as a parameter for a module, rules can change depending on the age of a plant segment, allowing animations of the entire life-cycle of the tree to be created.

Bi-directional grammars

The bi-directional model explicitly separates the symbolic rewriting system from the shape assignment. For example, the string rewriting process in the Example 2 is independent on how graphical operations are assigned to the symbols. In other words, an infinite number of draw methods are applicable to a given rewriting system.
The bi-directional model consists of 1) a forward process constructs the derivation tree with production rules, and 2) a backward process realizes the tree with shapes in a stepwise manner. Each inverse-derivation step involves essential geometric-topological reasoning. With this bi-directional framework, design constraints and objectives are encoded in the grammar-shape translation. In architectural design applications, the bi-directional grammar features consistent interior connectivity and a rich spatial hierarchy.

Open problems

There are many open problems involving studies of L-systems. For example:
L-systems on the real line R:
Well-known L-systems on a plane R2 are: