L-Systems

An L-system, or Lindenmeyer system is a rewriting system for generating structured strings of symbols. The idea is named for Aristid Lindenmeyer who invented it to help him model the growth of algae and other simple organisms. An L-system consists of the following:

• An alphabet of symbols. These are the symbols used in strings that belong to the L-System
• An axiom which is a string consisting of symbols from the alphabet and is considered to be the start point.
• A set of production rules. The production rules define the method for obtaining a new string from an existing string.

In the simplest L-systems, each production rule is defined by a single symbol and the sub-string with which it will be replaced in the new string. To obtain a new string from an old one, you apply the production rules to all of the symbols in the old string. L-systems of this type are called context free L-systems because the application of a production rule to a symbol depends only on that specific symbol.

All of this will be clearer if we look at a simple example. This is one of Lindenmeyer’s original examples.

The alphabet consists of the letters A and B.

The axiom is B.

The production rules are:

• A → AB
• B → A

The above means that, in a string, every A is to be rewritten as AB and every B is to be rewritten as A.

Starting with B, our axiom, we can only apply the second production rule which gives us A. Next we can only apply the first production rule to give us AB. With this string, we apply the first production rule to the A and the second production rule to the B and that gives us ABA. In the next iteration, we replace both occurrences of A with AB and the B with A. The first few iterations are as follows:

B
A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB

An interesting property is that the number of A‘s in each string is the same as the total number of letters in the previous string and the number of B‘s is the same as the number of A‘s in the previous string and therefore the total number of letters in the string before that. The lengths of the strings are the Fibonacci numbers.

We always apply the rules simultaneously to all the symbols and the sequence of strings produced is deterministic. Later, we will talk about L-systems where this may not be the case.

A more complex L-system:

Alphabet: 0 1 [ ]

Axiom: 0

Production rules:

• 0 → 1[0]0
• 1 → 11

You’ll note that there are no production rules given for the symbols [ and ]. If no production rule is given for a symbol, we assume an implicit rule that replaces the symbol with itself i.e. leaves it unchanged. So, in the above system, the rules [ → [ and ] → ] are assumed to exist. Sometimes we call symbols that have such an implied rule constants because once a string contains one, it never gets replaced or goes away.

The first few strings, in this case are:

0
1[0]0
11[1[0]0]1[0]0
1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0

This is all very nice and we can now generate nice long strings of symbols at will, but the real strength of L-systems is in what we do with the strings of symbols once we have got them. The traditional thing to do is to map each symbol onto a command for a turtle e.g. swim straight ahead, go left, crawl up the beach and lay eggs.

No, I mean commands for a graphics turtle as used by the Logo programming language. As an example, let’s look at another L-system.

Alphabet: F + –

Axiom: F++F++F

Production rule:

• F → F-F++F-F

Here’s a couple of iterations of applying the rules

F++F++F
F-F++F-F++F-F++F-F++F-F++F-F
F-F++F-F–F-F++F-F++F-F++F-F–F-F++F-F++F-F++F-F–F-F++F-F++F-F++F-F–F-F++F-F++F-F++F-F–F-F++F-F++F-F++F-F–F-F++F-F

There are three lines above, but the last one may wrap round because it is very long. If we give the symbols the following meanings in turtle commands:

• F → Move forward with the pen down
• + → Turn right 60 degrees
• – → Turn left 60 degrees

this will draw us a picture. Here’s a rendering of what the picture will look like:

The green lines represent the turtle path. This is the third iteration of the fractal snow flake curve. Each application of the production rule in the L-system gives us the next “level” of the fractal.

The image may look a bit odd, because it is rendered using Apple’s 3D rendering kit SceneKit. It’s actually drawn vertically in a 3D space on a partially shiny surface. Obviously, for the snow flake curve, this is unnecessary overkill, but future renderings may need 3D graphics.

The code used to draw the above image is available here. It’s a SwiftUI application that embeds the SceneKit scene.

In the next post, we’ll talk about more complex L-systems and how they can be used to model simple plant-like structures.