Lindenmayer Grammars

The Lindenmayer system was originally formulated in 1968 by Aristid Lindenmayer, a biologist who was studying algae growth at the time. He wanted a way to test his theory about the growth pattern of a particular type of algae. His theory stated that the cells of this algae could be in one of two states: growth or reproduction. An algae in the growth state eventually grew into the reproduction state. An algae in the reproduction state eventually divided into two cells, one of which was in the growth state and the other in the reproduction state. Lindenmayer's grammar system proved a fantastic method for proving his theory. What Lindenmayer could not have predicted is the incredible usefulness of his system in many other areas, both in biology and in mathematics.

A Lindenmayer grammar is fully defined by an initial axiom and a set of one or more transformation rules. The initial axiom consists of a "string" of characters (e.g., alphabetic letters, punctuation, etc.). Each transformation rule gives a set of characters to search for in an axiom, and a set of characters to replace the original characters with. Applying all of the transformation rules to the initial axiom produces a new axiom. The rules can then be applied to this second axiom to produce a third axiom. Applying the rules to the third axiom produces the fourth, and so on. Each application of the transformation rules is called an iteration of the grammar.

As an example, we model Lindenmayer's own algae theory. We call the reproduction state a, and the growth state we denote by b. Let us say that we start with one algae in the growth state. Thus, the initial axiom is simply b. Lindenmayer's theory describes two transformation rules: (1) b > a and (2) a > ab. The first rule states that occurrences of b are to be replaced with a and the second rule states that occurrences of a are to be replaced with ab. We now apply these rules to produce new axioms. The initial axiom b is transformed by (1) into a. This is then transformed by (2) into ab. Now, (2) transforms the a into ab and (1) transforms the b into a, to produce aba. Note that, after applying (2), we had abb, but then (1) was only applied to the second b, because the first b was not part of the axiom before any transformations occurred. The next iteration produces abaab, then abaababa, then abaababaabaab, and so on. The diagram on the left illustrates this process.

Of course, a Lindenmayer grammar can have any number of transformation rules of any complexity, and there is no limit to the length of the initial axiom.