The Lindenmayer system or L-system is a specialisation of the type of systems called production systems. They are based on string substitution using very specific rules. The specialiation that L-systems have is that the string that describes them is a tree structure.

This is an important distinction because L-systems, in general, need to be able to branch. The branch in an L-system could be described as a backtrack rather than a branch, but really it is the same thing as you will see.

A very simple L-system is defined as follows:

Axiom: **B**

Rules:

**B** -> **F{-B}+B**

**F** -> **FF**

The axiom is the starting string and the rules describe how the system is allowed to develop. At each stage all the rules that can be applied are applied; each time this is done is called an iteration. This system will develop as follows:

**B**
**F{-B}+B**
**FF{-F{-B}+B}+F{-B}+B**
**FFFF{-FF{-F{-B}+B}+F{-B}+B}+FF{-F{-B}+B}+F{-B}+B**
This example seems meaningless until you realise that the brackets are delimiters which represent different levels of the tree. That way the second string in the expansion of **B** will look as follows:

**F**
/ \
-**B** +**B**
This expands to:
**F**
__ **F** __
/ \
_-**F**_ _+**F**_
/ \ / \
-**B** +**B** -**B** +**B**

It is quite a simple concept that the brackets allow a symbol to have many relationships to other symbols.

Another way to think of the brackets is a type of simple memory where "**{**" represents the instruction "save current position and orientation" and "**}**" represents "recall last position and orientation saved". Using this idea we can say that "**F{-B}+B**" means: (**F**) write **F**, (**{**) store the position of **F**, (-**B**) write "-**B**" at a level down from **F**, (**}**) go back to **F**, (+**B**) write "+**B**" at a level down from **F**.

We now have a way to make tree data structures from string substitution. This, on its own, is a powerful concept but fractals are beautiful and so we will want to draw them. This system already contains all we need to actually draw the fractal using a turtle. Seymour Papert invented the concept of a turtle graphics. It is a simple relative drawing system which uses a cursor (the turtle) that is capable of moving, drawing lines, rotating and saving and recalling previous positions and orientations.

The symbols in this system mean:

**B**: Draw a line of length 1

**F**: Draw a line of length 2

**{**: Save position and orientation (push the position and orientation onto a FIFO stack)

**}**: Recall last position and orientation (pop the position and orientation from the FIFO stack)

**-**: Rotate turtle -45^{o} (or any angle you care to experiment with)

**+**: Rotate turtle 45^{o}

The drawing stage of the algorithm is the final stage. It is better to run the expansion for a number of iterations and then draw the (now huge) string using the rules above.

This algorithm can be used to create many familiar fractal types including: Ferns (of so many different types), Sierpinski squares and traingles (in many different ways), Koches, Koch Islands, Snowflakes, Penrose tiles and dragon curves.

Source:
G.W. Flake, "The Computational Beauty of Nature", MIT Press, 1999.