## L-systems

Notes published

Biologist Aristid Lindenmayer created Lindenmayer systems, or L-systems, in 1968 as a way of formalizing patterns of bacteria growth. L-systems are a recursive, string-rewriting framework, commonly used today in computer graphics to visualize and simulate organic growth, with applications in plant development, procedural content generation, and fractal-like art.

The following describes L-system fundamentals, how they can be visually represented, and several classes of L-systems, like context-sensitive L-systems and stochastic L-systems. Much of the following has been derived from Przemyslaw Prusinkiewicz and Lindenmayer’s seminal work, The Algorithmic Beauty of Plants.

## String Rewriting

Fundamentally, an L-system is a set of rules that describe how to iteratively transform a string of symbols. A string, in this context, is a series of symbols, like “

$a$” or “$ababaabaaaa$

*production*, describes the transformation of one symbol to another symbol, series of symbols, or no symbol at all. On each iteration, the productions are applied to each character simultaneously, resulting in a new series of symbols.

Productions in this rewriting system can be described with “before” and “after” states, often described as the *predecessor* and *successor*; for example, the production

represents that the symbol $a$

transforms into the symbols $ab$

on every iteration. The length of derivation, or the number of iterations, is represented by $n$

. Given a word $a$

and productions $a longrightarrow ab$

and $b longrightarrow a$

, the following illustrates how the word transforms over several iterations, from $n=0$

to $n=4$

.

### Formalizing L-systems

L-systems are formalized as a tuple with the following definition:

$G = langle V, w, P rangle$

Where the components are:

- $V$
- $w$
- $P$

The L-system in **Figure 1** can be formalized by defining its *axiom* (

) and a series of productions ($p_{1}, …, p_{n}$

) as:

$begin{aligned}$

w &: a \

p_{1} &: b longrightarrow a \

p_{2} &: a longrightarrow ab \

end{aligned}

The alphabet of all valid symbols can be inferred. It is implied that a symbol without a matching production has an identity production, e.g.

$a longrightarrow a$.

### D0L-systems

This fundamental form of an L-system is described as a deterministic, context-free L-system, or D0L-system (or sometimes *DOL-system*). 0L-systems are context-free, meaning that each predecessor is transformed regardless of its position in the string and its neighbors. *Deterministic* L-systems always produce the same result given the same configurations, as there is only one matching production for each predecessor.

## Graphical Representation of L-systems

L-systems can be represented visually via turtle graphics, of Logo fame. While L-systems are string rewriting systems, these strings are comprised of symbols, each which can represent some command. A turtle in computer graphics is similar to a pen plotter drawing lines in a 2D space. Imagine giving instructions to a pen plotter to draw a square: “*draw 1cm. turn right. draw 1cm. turn right. draw 1cm. turn right. draw 1cm*“. Though plotters don’t really have an orientation, an L-system’s turtle can be represented by Cartesian coordinates

and $y$

, and an angle $alpha$

that describes its forward direction. From there, symbols in a string can represent commands to change the state of the turtle.

To move a turtle around in 2D, symbols must be chosen to represent movement and rotation. The symbols

$F$, $+$

and $–$

will be used here, as they are commonly selected for these commands in L-system interpreters. After deriving the result of an L-system using its production rules, the string can then be parsed from left to right, with the following symbols modifying the turtle state:

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

The variables

$delta$and $d$

are global values indicating the magnitude of each symbol’s rotation or movement. In non-parametric L-systems, each symbol’s rotation and movement magnitude is a constant in the system.

Following the line in **Figure 2** from the bottom left corner, the string can be read as *“forward, forward, forward, right, forward, forward, right…”* and so on.

A turtle may be decoupled from an L-system. The L-system has a starting string and a set of productions and outputs the resulting string. A turtle may take that final string as an input, and output some visual representation. For example, many of the illustrations shown here use the same L-system solvers, while using different turtles where appropriate, like one turtle built using CanvasRenderingContext2D and another using WebGL.

### Space-Filling Curves

Space-filling curves can be formalized via L-systems, resulting in a recursive, fractal-like pattern. More specifically, FASS curves, defined as space-**f**illing, self-**a**voiding, **s**imple, and self-**s**imilar. That is, a single, non-overlapping, recursive, continuous curve.

$begin{aligned}$

delta &: 90 \

w &: X \

p_{1} &: X longrightarrow + Y F – X F X – F Y + \

p_{2} &: Y longrightarrow – X F + Y F Y + F X – \

end{aligned}

The Hilbert Curve (**Figure 3**) is an example of a FASS curve that can be represented as an L-system. Considered a Node-rewriting technique, this L-system’s productions declare that on each iteration,

and $Y$

symbols are replaced with more $F$

, $X$

and $Y$

symbols. With the angle $delta$

square wave shape along a curve. While

defined as 90, this results in recursively generated $F$, $+$

and $–$

are interpreted by the turtle, other symbols can be used for productions. In this case, $X$

and $Y$

are ignored when rendering, and only relevant when rewriting the string and matching productions.

### 3D Interpretation

In addition to a turtle traversing on a 2D plane, symbols may be introduced that instruct the turtle to draw in 3D. The Algorithmic Beauty of Plants uses the following symbols to control rendering in three dimensions:

- $+$
- $–$
- $&$
- $wedge$
- $backslash$
- $/$
- $|$

Like the 2D Hilbert Curve (**Figure 3**), a three-dimensional version can also be created (**Figure 4**) using these additional symbols, resulting in a 3D FASS curve.

$begin{aligned}$

delta &: 90 \

w &: X \

p_{1} &: X longrightarrow & wedge backslash X F wedge backslash X F X \

& & – F wedge / / X F X \

& & & F + / / X F X \

& & – F / X – / \

end{aligned}

## Bracketed L-Systems

The space-filling Hilbert curve can be represented as a single, continuous line. For organic, tree-like structures, *branching* is used to represent a diverging fork. Two new symbols, square brackets, are introduced to represent a tree in an L-system’s string, with an opening bracket indicating the start of a new branch, with the remaining symbols between the brackets being members of that branch. Symbols after the end bracket indicate returning to the point of the branch’s origin. A stack is used to implement branching, storing the state of the turtle on the stack.

- $[$
- $]$

Symbols in a branch are transformed and replaced just as they were outside of a branch. This allows recursive, fractal-like behavior, with each branch forking into more branches, and so on.

## Context-sensitive L-systems

Rather than productions evaluating symbols in isolation (context-free), rules may be defined that only matches a symbol when it proceeds or succeeds another specific symbol.

Context-sensitive L-systems contain production rules that specify symbols that must come before or after the predecessor in order to match, as opposed to context-free systems that evaluate predecessors in isolation.

These context rules are defined using

$<$and $>$

**Figure 5**, the first production rule only matches when the

symbol is immediately after $b$

, thus replacing the $a$

predecessor with its successor, $b$

. This results in the $b$

symbol moving towards the right:

$begin{aligned}$

&baaaa \

&abaaa \

&aabaa \

&aaaba \

&aaaab \

end{aligned}

A similar system could be defined that propagates

$b$from right to left, defined via production $a > b longrightarrow b$

, replacing $a$

when there is a $b$

after it in the string.

L-systems with these one-sided context productions may be considered 1L-systems. Productions may also have both a before-context and an after-context in systems considered 2L-systems. They can be represented as:

$A < X > B longrightarrow Y$

This production rule indicates that the predecessor

$X$will be replaced by successor $Y$

when it is between an $A$

and a $B$

.

## Stochastic L-systems

The previously described systems are all deterministic; the same system with the same input will always generate the same result. Stochastic L-systems are non-deterministic, defined by several productions that match the same predecessor, chosen randomly given their weight on each iteration. The following production rules define that on each iteration,

$X$has a 50% chance to be rewritten as $A$

, and a 50% chance to be rewritten as $B$

.

$begin{aligned}$

X & xrightarrow{.5} A \

X & xrightarrow{.5} B \

end{aligned}

This non-determinism is useful for procedurally creating variety and the seemingly random results of nature.

## Resources

**Original Source**