Basic definitions

Lindenmayer systems, or L-systems for short, are a particular type of symbolic dynamical system with the added feature of a geometrical interpretation of the evolution of the system. They were invented in 1968 by Aristid Lindenmayer to model biological growth. The limiting geometry of even very simple systems can be extraordinary fractals.

Because of the elegance of the systems and the beauty of the fractals, they are extremely popular and there are several fine resources for learning about them on the web, including the following:

• L-systems tutorial at Australian National University
• the L-systems page in the FRACTINT manual

In addition, there are now many excellent and striking books on L-systems, including [PL90, PH89, RS80, RS92], from which we shall borrow heavily.

Rather than reproduce all that, here we shall start a bit more abstractly with a symbolic dynamical system. The components of an L-system are as follows:

Alphabet:

The alphabet is a finite set V of formal symbols, usually taken to be letters a, b, c, etc., or possibly some other characters.

Axiom:

The axiom (also called the initiator) is a string of symbols from V. The set of strings (also called words) from V is denoted . Given , some examples of words are aabca, caab, b, bbc, etc. The length |w| of a word w is the number of symbols in the word.

Productions:

A production (or rewriting rule) is a mapping of a symbol to a word . This will be labelled and written with notation:

We allow as possible productions mappings of a to the empty word, denoted , or to a itself. If a symbol does not have an explicitly given production, we assume it is mapped to itself by default. In that case, a is a constant of the L-system.