L-Systems; the L's for Lindenmayer

Crikey, there’s a lot of jargon here, but remember: a grammar describes how to form strings from an alphabet that are valid according to some syntax. It doesn’t define meaning. It generates strings using production rules.

Chomsky defined a hierarchy of grammars of increasing generative power; in one type, context-free grammars, the production rules for a symbol don’t depend on other symbols in the string.

L-systems comprise a context-free grammar and a mechanism for translating generated strings into geometric structures. Aristid Lindenmayer used them to formally model the growth of plants; see The Algorithmic Beauty of Plants.

They grammar comprises an alphabet containing two sets of symbols: those that can be replaced, and those that cannot (known as terminals); and a set of production rules define how a single symbol can be translated into one or more symbols, including themselves in the case of terminal symbols. The rules are generally applied iteratively, starting with an axiom or initial state. A vocabulary provides the mechanism for attributing a (geometric) meaning to a string, attributing an action (like draw a line segment, or branch at a given angle) to each symbol.

I’ve inevitably used the technical term “vocabulary” incorrectly. Can some rules destroy symbols? Something to think about.

Underneath this complexity they’re quite simple to implement. Lindenmayer modelled growth of filaments of Anabaena catenula with a simple L-system, simply representing each cell’s size and readiness to divide as one of two states, labeled A or B. I’m inferring from the system’s rules that A implies ready-to-divide, while B is some early growth state. In C#, Lindemayer’s simple model for algae looks like:

And to process it - or any similar system to, say, the 5th iteration, we can just use:

Finally we can attribute meaning to the generated string - a simple meaning in this case, as we’ll just write out the string to represent the resulting series of states:

which shows us the 5th iteration is: ABAABABAABAAB.