July 28, 2017
About 12 minutes
Visualization Morphogenesis Strings Languages STEM

Lindenmayer systems

Describing how things grow with strings of letters

Natural processes as computation

Lindenmayer systems, or L-systems, describe how living things can develop complex forms by the repeated application of simple rules. Aristid Lindenmayer (1925–1989), the theoretical biologist who proposed L-systems in 1968,¹ first used them to describe the growth patterns of algae. This page is (mostly) algae-free, but it does let you explore Lindenmayer systems by making plant-like structures,² classic fractals, and other designs.

Introduction

The natural world produces amazingly complex systems from simple starting points. In biology, computational models have played a critical role in helping scientists understand how these complex systems can develop. L-systems are one of the better-known of these models. In L-systems, structures develop through a process of string rewriting. A string of letters is transformed into a new string of letters using simple rules called productions. The process is repeated indefinitely, each time using the string that was just produced as the source for the next string. Because the strings tend to grow with each rewrite, an L-system can become arbitrarily complex, but always guided by a simple process dictated by a fixed set of simple rules.

Before getting into more detail, take a moment to play with the app below. Try changing the Order and drawing the result. Try drawing orders 0, 1, 2, 3, and 4 in order and observe the progression. Then try some other example systems to get a feel for what’s possible (there are over 50!). Feel free to play around, but know that behind the scenes L-system strings can grow very quickly as the order increases. The longer the string, the longer it will take to draw the result! Your browser may even run out of memory, which will “crash” the page—but with no real harm done. Just reload the page and choose different settings!

How L-systems work

L-systems repeatedly rewrite a string according to some simple rules: You start from a string called the axiom. Think of it like a seed: it is the starting point that the system grows from. Regulating that growth is a set of rules, called productions. By applying the productions to the axiom, you will make new strings that represent one “step” of growth. To get the next growth step, you feed the result of the previous step back into the system by applying the productions again.

All the strings you can produce this way are said to be in the language of the L-system.

Let’s look at a simple example:

axiom Y
Y → XYX

This system has only production, the rule Y → XYX. To apply it, you scan a string that is known to be in the system’s language from left to right, and anywhere you see the pattern on the left of the → symbol, you replace it with the pattern on the right side. Let’s see how that would work.

To start with, we only know of one string in the language, the axiom Y. But we see that we can produce XYX by applying the production Y → XYX. So now we know that XYX is also in the language. We can use that to produce a new string, too. There is no production with X on the left side, so those won’t change. But the Y in the middle can be changed to XYX again, giving the string XXYXX. That’s also a string in the language, which you can rewrite again, and so on.

Ordered L-systems

With this system, you can soon see that each time you apply the production you will get exactly one new string. It will be just like the one you started with but with another X added to either side of the Y. When an L-system can only make one new string each time it is rewritten, we often talk about the system’s “order n” string. The order 0 string is the axiom. The order 1 string is made from the order 0 string. The order 2 string is made from the order 1 string, and so on. That’s why the app above has a control named Order: it uses the string of that order to produce the drawing.

Not all L-systems work this way. For example, what would happen if we extended the system above as follows?

axiom Y
Y → XYX
YX → XY

This system starts the same, producing Y and then XYX as before. After that, you run into a problem: two different rules can be applied at the same spot. You can replace the Y with XYX, or you can replace the Y and the following X with XY. Which to choose? There are different ways that this can be handled, but what if you allow both possibilities? Then instead of having one definitive string for each generation, you have sets of strings leading to more sets of strings! As you can imagine, systems that allow rules like these become very complex, very quickly. On this page, all of the L-systems are of a subtype called d0L-systems. A d0L-system has a couple of restrictions which guarantee that our systems are nicely ordered:

1. the left-hand side of a production can only be a single letter; and
2. no two productions can have the same left-hand side.

The rest of this article deals exclusively with d0L-systems. Don’t feel cheated—they offer lots of possibilities.

From strings to nature

So far we’ve seen that L-systems can grow strings very well. How does that connect to the natural world? We can get a whiff of that connection by going back to Lindenmayer’s original work with algae growth patterns. Here is a system from his original paper:

axiom B
A → AB
B → A

If you write the first 8 orders of this system you’ll get B, A, AB, ABA, ABAAB, ABAABABA, ABAABABAABAAB and ABAABABAABAABABAABABA. Notice a pattern? If not, look closely at the length of each of these strings: 1, 1, 2, 3, 5, 8, 13, 21. Can you see why the strings produced by this system are called Fibostrings? Quite apart from how algae grow, you probably remember learning that the Fibonacci number sequence shows up often in the natural world, most famously in the way that leaves and scales are arranged on plants (phyllotaxis).

Enter the turtle

Still, as exciting as it is to know that you can whip yourself up some Fibostrings anytime you’re in the mood, it still seems a big leap to the images produced by the app above. To bridge the gap we need to give the strings a geometric interpretation. The demo does this using “turtle graphics”, on odd name which comes from the Logo programming language.

Turtle graphics work like this: Imagine you’re a turtle on an infinitely large piece of paper. And not just any turtle, but one that can understand simple instructions and that has a basic understanding of angles and distances. Finally, imagine that you (the unusually bright turtle, that is) also have a pen in your mouth.

Have you got that image in mind? Good.

Now suppose I give you instructions like this:

1. Touch the pen to the paper.
2. Move forward 1 step, turn left 90°.
3. Move forward 1 step, turn left 90°.
4. Move forward 1 step, turn left 90°.
5. Move forward 1 step.

You’ve just drawn a square.
   🐢 What a good little turtle you are!

Now imagine what a hard-working (virtual) turtle could do with our L-system strings if we associate some of those symbols with instructions like “move forward 1 step”. Here is an example:

axiom FX
X → -FX++FY-
Y → +FX--FY+
F →

Notice that F produces an empty string. That just means we will delete any F symbols when we rewrite the string.

Now if the turtle interprets the symbol F to mean “move forward 1 step with pen down”, the symbol - to mean “turn right 45°” and the symbol + to mean “turn left 45°” then the order 8 string of this system will make the turtle draw this picture:

If you are interested in fractals, you may recognize this as a dragon curve. Pretty neat, but it still doesn’t seem to offer much insight into how plants grow!

Trees and branches

To draw plant-like structures, we need to extend the turtle’s capabilities a little bit further. To see why, it is useful to consider this rule for drawing a simple tree:

To draw a tree, draw a trunk with two shorter trees coming out of the top at a right angle to each other.

Notice that this definition is self-referential or recursive: part of a tree is two shorter trees! How can we make any sense of that? One step at a time. Start by drawing a trunk: a straight vertical line. Now since a tree has “two shorter trees coming out” of the trunk, start off those trees by drawing two shorter trunks to make a Y shape. But don’t stop there. Since each branch of the Y is the trunk of a new tree, you need to add two shorter trunks to them as well. And since each of those new branches is also the start of a tree, they need trunks… you can continue as many times as you like, each time extending the tree a little in the same way that the next string in an L-system builds on the previous one. After the first three steps, your tree should have progressed through these stages:

And if you keep on going you will end up with something like this:

Which is indeed rather tree-like! So, what new capabilities does our turtle need to recreate this process? The recursion is no problem: in fact, all the L-systems above use recursion whenever the symbol on the left-hand side of a production rule also appears somewhere on that rule’s right-hand expansion (either directly, or indirectly from another rule).

One capability that’s missing is changing the turtle’s step size so we can make shorter trees on top of our trunks. No problem, we can add a new symbol, @, for that.

You can optionally follow @ with a number that you want to mulitply the step size by.

We will also need a way to give the turtle some kind of memory. Now this one is a little trickier! We need a memory in order to create the two branches: after we draw the first branch, we need a way to get back to where we started so we can draw the second one.

The turtle’s memory will be controlled with two new symbols: [ and ]. The [ symbol tells the turtle to write down its current state on a note and put that note on top of a special stack of such notes. The ] symbol tells the turtle to take the top note off the stack and recreate the same state that is written there. The turtle’s state includes its position, direction, step size, and other information: anything that would change how it draws a line.

Actual plants don’t have a memory, of course, but we only have one turtle to draw the whole tree. On a real plant each branch starts growing from a bud that is effectively a new turtle just for that branch. In fact, you might find it helpful to think of [ and ] as representing a bud, and everything between those symbols as what will grow from it.

Whew! Putting this all together, we can finally recreate our simple tree as an L-system:

axiom FX
X → @[+FX][-FX]

Let’s look at each symbol in turn: The axiom is F (draw a line for the trunk) followed by X (a placeholder that will be replaced by “two shorter trees”). The production will rewrite the X as @ (make the step size shorter), [ (start a new branch), + (turn left 45°), FX (a new trunk, and a new tree placeholder), ] (finish the branch, returning to where the branch started), [ (start a second new branch), - (turn right 45°), FX (the second new tree), ] (finish the second branch). The turtle instructions are an exact analogue of our tree-drawing rule!

The second [ and ] in that production are not actually necessary. You will get the same series of drawings with @[+FX]-FX. I leave it an as exercise for you to figure out why.

Playtime!

Now you are ready to go back to the app and explore more examples or try creating systems of your own. There are just a couple of things to note: First, when defining a production, the app uses = instead of → (it’s a lot easier to type!). And second, by default, the turtle will turn in 45° increments. To change that add a line like this: angle n, where n is the number of turns that should make up a complete circle. (There are more commands, but that’s enough to get started. When you are ready, a complete list follows below.)

Happy string rewriting!

Command reference

The commands used by the app have been chosen to be mostly compatible with the fractal software Fractint, though the two systems are not identical. One difference of note is that this system is case-sensitive, while Fractint is not.

Preamble directives

Productions

Drawing symbols used in productions

Colours

The turtle has a palette of 256 different pen colours. The palette has been chosen to let you draw a wide variety of designs with nice results. It blends smoothly from brown to green, cyan, blue, indigo, violet, red, orange, pale yellow, and finally back to brown. Using > and < you can move through the palette in either direction; if you move past the first or last colour, you will wrap back around to the other end.

Bibliography

1. Aristid Lindenmayer. Mathematical models for cellular interaction in development. Journal of Theoretical Biology, 18:280–315, 1968. ↩︎

2. Przemysław Prusinkiewicz and Aristid Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, 1990. ↩︎