A Brief History of Lindenmayer Systems

For as long as there have been mathematicians, there have been mathematicians who are fascinated by plants. Everyone has looked at them in wonder at one point or another in his/her life. There have been, naturally, attempts made to try and model their growth.

The precursor to L-systems (which was not actually related to modeling plant growth) were Chomsky grammars. The precursor to Chomsky grammars was a string rewriting algorithm devised by a person named Thue. Chomsky's work was on grammars and how they can be used to describe natural languages. This sparked quite an interest in the field of string rewriting.

In 1968 Aristid Lindenmayer introduced a new string rewriting algorithm that was very similar to what Chomsky used. The big difference was that L-systems were a parallel replacement algorithm. That means that the effect of an L-system is the same as if You looked at the initiator and replaced all the occurances of what the generator was replacing (r and any line, in our two examples from the previous page) at the same time. Chomsky's algorithm replaces one at a time, and re-evaluates the whole thing every time it does a replacement. That means that in our two examples, the first iteration would be rruuldlu, and the second iteration would be rruulruullu. In the second example, the process would infinitely replace only one side of the initiator for each iteration.

The reason for the difference is that when Dr. Lindemayer was using his method, he was thinking of plants. Plants work in parallel. Cells are constantly regenerating independantly, so a whole bunch could regenerate at the same time - like in an L-system.