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 neighborhood 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 exciting as they provide a mechanism for keeping track of fractal structures that require complex and multifaceted production rules.
How To Build
Composition
Let us 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 merely a transform taking a symbol as a 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; we will now 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 merely apply the first rule for A.
In the second iteration we have to apply the rules for A and 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 us see how those strings become descriptions of curves!
Visual Representation
Recursive Lsystems, like the one described above, often produce intricate 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 typical graphical way of representing LSystems is based on Turtle Interpretation (working as LOGO programming, an ancient [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 particular angle)
 : Turn right (of a particular angle)
 [: Push current location
 ]: Pop location
Example
We will 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 is 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 precisely one production rule for each symbol,
then the Lsystem is said to be deterministic.
If each production rule refers only to a particular symbol and not to its neighbors,
then the Lsystem is said to be contextfree.

Stochastic contextfree System or S0LSystème
If there are several production rules 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.