Quick Access
Description
In 1968, the Hungarian botanist Aristid Lindenmayer developed a grammarbased system to model and simulate the growth patterns of plants. Originally the LSystems (short term for Lindenmayer systems) were devised to provide a formal description of the development of simple multicellular organisms while illustrating the neighbourhood relationships between plant cells. Later on, this system was extended to describe higher plants and complex branching structures.
The realistic modeling of plant growth is of very high value to biology, physics and also for computer graphics (e.g. video games are using and still working on it to improve plants/forests rendering).
We will see how it works and use them to generate all kind of recursive fractal patterns. They are incredibly interesting as they provide a mechanism for keeping track of fractal structures that require complex and multifaceted production rules.
How To Build
Composition
Let’s quickly see the composition of the LSystems, it involves four main components:

Alphabet: Contains the valid symbols that can be managed.
For example, we could say the alphabet is {‘F’, ‘X’, ‘Y’} meaning that any these three characters
could be replaced given a rule.

Constants: Symbols that do not get replaced.
Most of the time the constants contains at least
!, [, ], +, 
(cf. Visual Interpretation) and are used for graphical instructions.

Axiom: The axiom describes the initial state of the system
(at iteration 0). It could be for instance “F”, “FX”, “FFF” or anything else.
 Rules: A rule is simply a transform taking a symbol as parameter. The rules are applied successively to each symbol of the axiom and then over and over again at each iteration. If we take the rule “A —> AB”: whenever an “A” symbol is found in the current state, it is replaced with “AB.”
We have now everything to build a simple example; let’s study the Lindenmayer’s original system for modeling the growth of an algae.
Example
 Alphabet: A, B
 Constants: none
 Axiom: A
 Rules: (A → AB), (B → A)
The system starts with “A” which is the axiom (iteration 0) and has two productions, one for A and one for B; have a look at the first five iterations:


For the first iteration we simply apply the first rule for A.
In the second iteration we have to apply the rules for A and for B etc. etc.
The derivations grow exponentially as a single letter often gets replaced
by two or more letters in each iteration.
PseudoCode
string LSystem(axiom, rules, depth) { string production; // For each iteration: for (auto level = 0; level < depth; ++level) { // Initialize production to empty string at each iteration production = ''; // Iterate over each symbols/characters of the current axiom for (auto symbol = axiom.begin(); symbol < axiom.end(); ++symbol) { // Transform it if a rule applies if (rules.has(symbol)) production += rules.get(symbol); // Add it without change otherwise else production += symbol; } // Update the axiom to its new content axiom = production } return production; }
The recursive nature of the Lsystem rules leads to
selfsimilarity and thereby fractallike forms.
Now, let’s see how those strings become descriptions of curves!
Visual Representation
Recursive Lsystems, like the one described above, often produce intricately complex patterns that are selfsimilar across multiple scales.
These patterns are almost impossible for a human to perceive directly from long strings of symbols. As with many types of data, a graphical representation may expose them.
The most common graphical way of representing LSystems is based on Turtle Interpretation (working as LOGO programming, a very old [1967] kid friendly way of teaching computer science with a Turtle), that draw by means of commanding a turtle in a Cartesian plane.
Imagine a turtle sitting on your computer screen to which you could issue a set of commands: move forward, turn left, turn right, draw a line, etc.
Now, we can associate each symbol to one command; the following dictionary is commonly used with LSystems:
 F: Draw a line forward (demo default direction forwarding East)
 G: Move forward (without drawing a line)
 +: Turn left (of a certain angle)
 : Turn right (of a certain angle)
 [: Push current location
 ]: Pop location
Example
Let’s interpret the string F  F  F  F with a turning angle of 90◦ and starting facing north. While you can already imagine the final drawing, here is the Turtle making it:
! It's time to produce a fractal !
Visualization Analysis
We will create a Koch Triangle fractal (described above) step by step.
 Alphabet: F
 Angle Turn: 60°
 Constants: none
 Axiom: F
 Rules: F → F+FF+F
LSystem Types
We have seen here the simplest LSystems to handle; however, more advanced systems exist and may be built. Here is the list of the different types that may be used:

Deterministic contextfree System or D0LSystem:
If there is exactly one production rule for each symbol,
then the Lsystem is said to be deterministic.
If each production rule refers only to an individual symbol and not to its neighbours,
then the Lsystem is said to be contextfree.

Stochastic contextfree System or S0LSystème
If there are several production rule for a symbol that is
chosen with a certain probability, then it is a stochastic Lsystem.

Context Sensitive System, ILSystem, or (k, l)System:
A context sensitive grammar looks not only at the symbol it is modifying,
but the symbols appearing before and/or after it
 Parametric LSystem: 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.