L-systems

String-rewriting systems developed by Aristid Lindenmayer (which is where the `L' comes from) which model plants quite successfully. An L-system is basically a set of symbols in an alphabet, a set of rules to apply to the alphabet, and a starting string of the symbols.

As an example, take the alphabet to be {a,b}. Take two rules:

b -> ab
a -> b

And use `a' as the initial string. The development of the system will go like this (where n is the generation of the system):

n	String
0	a
1	b
2	ab
3	bab
4	abbab
5	bababbab

This may not seem like much, but (if I've remembered it correctly) it's a good model for the development and cell growth of a real system. The details may be found in The Algorithmic Beauty of Plants. With the expansion of the alphabet, and the addition of a turtle-based interpretation of the strings (like LOGO), fractal shapes such as a Sierpinski gasket can be formed. With care, plant and leaf-like forms can be generated. The addition of stochastic rules adds variation to the final output of the L-system on each run.

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.