L-Systems, a Grammar That Grows Branches, math that surprises you lesson

Start with the single letter F and one rule, which replaces every F by F[+F]F[-F]F. After three rounds the string is more than three hundred symbols long, and when its symbols are read as drawing instructions they produce a branching, plant-like picture. Can such a short rule grow an intricate tree, and what exactly happens in one round? This page separates the two stages, rewriting the string and drawing it, and fixes the conventions that make each picture well defined.

Key terms

L-system

Definition An L-system, short for Lindenmayer system, consists of an alphabet of symbols, a starting string called the axiom, and production rules that say which string replaces each symbol. The L-systems on this page are the simplest kind, called deterministic and context-free. Each symbol has exactly one replacement, which does not depend on the neighboring symbols, and a symbol without a rule is replaced by itself. One generation rewrites every symbol of the current string at once, as the next card describes, and the strings obtained after $0, 1, 2, \ldots$ rounds are the generations of the system. To get a picture, the symbols of a generation are then read as commands for a drawing turtle. Rewriting and drawing are separate stages, and the same string can be drawn with different angles and step lengths. The biologist Aristid Lindenmayer introduced L-systems in 1968 to describe the growth of simple multicellular organisms such as algae. A short rule like the one below gives a plant-like drawing, but it is not a model of how a real plant develops. It has no response to light, no competition for water or nutrients and no bending under weight.

In plain words An L-system is a rule for growing a string of symbols, one generation at a time, together with a separate recipe for turning each string into a picture.

Example The axiom is F, and the only rule is

\texttt{F} \;\to\; \texttt{F[+F]F[-F]F}.

Generation $1$ is F[+F]F[-F]F, and generation $2$ is

F[+F]F[-F]F[+F[+F]F[-F]F]F[+F]F[-F]F[-F[+F]F[-F]F]F[+F]F[-F]F

The symbols +, -, [ and ] have no rule, so they are copied unchanged. Each round turns every F into eleven symbols, five of which are F, which gives these counts.

Generation	0	1	2	3
Symbols `F`	1	5	25	125
All symbols	1	11	61	311

String rewriting

Definition String rewriting builds a new string from an old one by replacing symbols according to rules. An L-system rewrites in parallel. It reads the complete old string, replaces each symbol by its replacement exactly once, and writes the results side by side, in the same order, to form the new string. Symbols created during a round belong to the new string and are not rewritten again until the next round. Rewriting newly made symbols during the same round would be a different process, and here it would never finish. The replacement of F begins with F again, so the first F could be expanded forever before the rest of the string is ever reached.

In plain words Every symbol of the old string is rewritten once, all at the same moment. Nothing written during a round is touched again until the next one, so each generation is one definite string.

Example To go from generation $1$ to generation $2$ , each of the five copies of F in F[+F]F[-F]F is replaced by F[+F]F[-F]F, and the brackets and signs between them are copied. Because a round treats each symbol separately, generation $n$ can also be found by applying $n - 1$ rounds to generation $1$ . Each of its five copies of F then grows into a copy of generation $n - 1$ , while the signs and brackets between them stay, so

\begin{gathered} G_n = G_{n-1}\texttt{[+}G_{n-1}\texttt{]} \\[0.4em] G_{n-1}\texttt{[-}G_{n-1}\texttt{]}G_{n-1}, \end{gathered}

for every $n \ge 1$ , where $G_n$ is the string of generation $n$ and the two lines are one string. So the number of symbols F is $5^n$ , and every round adds ten new symbols for each F of the old string, from $1$ to $11$ , then $11 + 50 = 61$ , then $61 + 250 = 311$ .

Turtle graphics

Definition Turtle graphics draws a string by reading its symbols from left to right as commands to an imaginary pen, the turtle. Its state is its position and its heading, the direction it faces. On this page the turtle starts at $(0, 0)$ facing straight up, each forward step has length $d$ , and each turn has the angle $\delta$ .

The symbol F moves the turtle forward by $d$ in the direction of its heading and draws a segment.
The symbol + turns it to the left, counterclockwise, by $\delta$ .
The symbol - turns it to the right, clockwise, by $\delta$ .
The symbol [ saves the current position and heading.
The symbol ] returns the turtle, without drawing, to the most recently saved position and heading that has not been used yet, and discards that saved state.

Every [ must have a matching ]. The picture depends on all of these choices, so two drawings can only be compared when the starting heading, the angle, the step length and the generation are all stated.

In plain words Imagine a pen that can walk forward, turn by a fixed angle and remember where it stood. A bracket lets it walk out along a branch and then jump back to the trunk, facing the way it faced before.

Example Draw generation $1$ with $\delta = 25^\circ$ and $d = \tfrac13$ . The turtle draws from $(0, 0)$ to $(0, \tfrac13)$ , saves that state, turns to face $25^\circ$ left of straight up, and draws a branch ending at about $(-0.1409, 0.6354)$ . It jumps back to $(0, \tfrac13)$ facing up, draws to $(0, \tfrac23)$ , saves, turns $25^\circ$ to the right, draws a branch ending at about $(0.1409, 0.9688)$ , jumps back, and draws to $(0, 1)$ . At generation $n$ take $d = 3^{-n}$ . The trunk, the steps that lie outside every bracket, then has $3^n$ steps that all point up, so it is always the segment from $(0, 0)$ to $(0, 1)$ , and new detail appears inside a fixed frame. By the five copies in the previous card, the drawing of generation $n$ consists of five copies of the drawing of generation $n - 1$ shrunk to a third, three stacked along the trunk, one turned $25^\circ$ to the left and starting at height $\tfrac13$ , and one turned $25^\circ$ to the right and starting at height $\tfrac23$ . These five shrinking maps form an iterated function system, so the drawings approach a single limiting shape. Changing only the angle keeps every string and changes the drawings from generation $1$ on. At generation $4$ the drawing is about $0.21$ wide at $15^\circ$ , $0.33$ wide at $25^\circ$ and $0.42$ wide at $35^\circ$ , and it is $1$ tall in all three cases.

Formal grammar

Definition A formal grammar describes a set of strings by rewriting. It has a finite alphabet, a starting string and a finite list of production rules, each allowing one string of symbols to be replaced by another wherever it occurs. In the grammars studied in linguistics and computer science, each step applies one rule at one place, chosen freely, so the same start can lead to many different strings. Such a grammar also marks some symbols as terminal symbols, which stand for the final letters, and the strings made only of terminal symbols that can be reached from the start form the language of the grammar. An L-system is a different kind of grammar. Every symbol is rewritten in each step, all at once, so the start leads to exactly one string in each generation, and every generation counts, not only the final strings.

In plain words A grammar is a list of allowed replacements. An ordinary grammar lets you make one replacement at a time, wherever you like, while an L-system makes all of them at once and so grows one definite string per generation.

Example Take the two rules that replace a by ab and b by a, and the axiom a. Parallel rewriting gives

a, ab, aba, abaab, abaababa, abaababaabaab

with lengths $1, 2, 3, 5, 8, 13$ . Each a produces two symbols and each b produces one, so the length of a generation is the previous length plus the number of copies of a in the previous generation. That number equals the length of the generation before it, since every symbol produces exactly one a. So from generation $2$ on, each length is the sum of the two lengths before it, the rule of the Fibonacci numbers. Rewriting one place at a time behaves differently. From ab, replacing only the a gives abb and replacing only the b gives aa, and neither is the next generation aba.

Check yourself

For the rule that replaces F by F[+F]F[-F]F, how many symbols F and how many symbols in all does generation $4$ have? Find a formula for the total number of symbols in generation $n$ .

Show the answer

Each round multiplies the number of symbols F by $5$ , so generation $4$ has $5^4 = 625$ of them. Each round adds ten symbols for every F of the old string, and generation $3$ has $311$ symbols and $125$ copies of F, so generation $4$ has $311 + 10 \cdot 125 = 1561$ symbols. In general the total is

\begin{aligned} L_n &= 1 + 10\,(1 + 5 + \cdots + 5^{n-1}) \\[0.4em] &= 1 + \frac{10\,(5^n - 1)}{4} \\[0.4em] &= \frac{5^{n+1} - 3}{2}, \end{aligned}

which gives $1$ , $11$ , $61$ , $311$ and $1561$ for $n = 0, 1, 2, 3, 4$ . With $d = 3^{-4}$ , the trunk of generation $4$ is made of $3^4 = 81$ steps of length $\tfrac{1}{81}$ .

Suppose a program makes a mistake, and ] restores the saved position but not the saved heading. What does it draw for generation $1$ with $\delta = 25^\circ$ and $d = \tfrac13$ , and where does the turtle end?

Show the answer

The first F draws from $(0, 0)$ to $(0, \tfrac13)$ , and the bracketed branch is drawn as before, up to about $(-0.1409, 0.6354)$ . Then ] puts the turtle back at $(0, \tfrac13)$ , but it keeps facing along the branch, $25^\circ$ left of straight up. The next F therefore draws the same branch again instead of the trunk. The second [ saves the point $(-0.1409, 0.6354)$ , the - turns the turtle back to straight up, and the F draws up to about $(-0.1409, 0.9688)$ . The last ] returns the turtle to $(-0.1409, 0.6354)$ , still facing up, and the final F draws the same vertical segment again. The turtle ends at about $(-0.1409, 0.9688)$ . The picture has only three different segments, the trunk stops at height $\tfrac13$ , and there is no right branch at all. Saving the heading together with the position is what lets the trunk continue in its own direction.

Remove the right branch from the rule, so that F is replaced by F[+F]FF, and keep $\delta = 25^\circ$ and $d = 3^{-n}$ . How many symbols F does generation $n$ have, how tall is the trunk, and what is generation $2$ ?

Show the answer

Each F now becomes four copies of F, so generation $n$ has $4^n$ of them. Three of the four lie outside the brackets, as before, so the trunk still has $3^n$ upward steps of length $3^{-n}$ and is still $1$ tall. Replacing each of the four copies of F in F[+F]FF gives generation $2$ ,

F[+F]FF[+F[+F]FF]F[+F]FFF[+F]FF

with $16$ copies of F and $31$ symbols. Every copy of the rule inherits the edit, so every branch now leaves its parent on the left, at every scale. One small change to the rule changes the whole picture, because the rule is reused everywhere.