Grammar Rules: How Parallel Rewriting Works

An L-system is a string rewriting system --- a set of rules for replacing symbols with other symbols. The output is a string of arbitrary length. The interesting content is what that string represents when interpreted geometrically. But the formal machinery is purely syntactic: symbols, rules, and substitution. Understanding the grammar precisely is a prerequisite for understanding why it produces the structures it does.

The Formal Definition

An L-system is a triple (V, omega, P):

V is the alphabet: a finite set of symbols. These are the vocabulary of the system. Common symbols in graphical L-systems include F, +, -, [, and ], but any finite set of symbols can serve.

omega is the axiom: a string over V that serves as the initial condition. Typically a single symbol, such as F.

P is a set of production rules. Each rule maps a symbol in V to a string over V. For example, F -> F[+F]F[-F]F says that every occurrence of F is replaced by the five-segment branching pattern F[+F]F[-F]F. A symbol not mentioned in any production rule maps to itself (the identity production).

At each time step (called a derivation step or generation), every symbol in the current string is simultaneously replaced according to its production rule. The result is a new string over V. The process repeats for a specified number of generations.

This simultaneous replacement is the defining feature that distinguishes L-systems from Chomsky grammars. In a Chomsky grammar (sequential rewriting), one symbol per step is selected and replaced. In an L-system, all symbols rewrite at once. The same production rules applied sequentially versus in parallel produce entirely different strings and, when interpreted geometrically, entirely different structures.

Lindenmayer chose parallel rewriting for a biological reason: in a growing organism, all cells act simultaneously. Cell A does not wait for cell B to divide before dividing itself. The grammar mirrors this concurrency.

Turtle Graphics Interpretation

The string produced by an L-system is abstract --- it has no inherent geometry. Prusinkiewicz introduced a geometric interpretation based on turtle graphics, a drawing framework where a “turtle” moves on a plane (or in 3D space) following commands encoded in the string:

F: Move forward by a fixed step length d, drawing a line segment.

f: Move forward by d without drawing.

+: Turn left (counterclockwise) by angle delta.

-: Turn right (clockwise) by angle delta.

[: Push the current turtle state (position, heading) onto a stack.

]: Pop the most recent state from the stack, restoring the turtle to its saved position and heading.

The bracket pair is what enables branching. When the turtle encounters [, it saves its state. It then follows the symbols inside the brackets, drawing a branch. When it encounters ], it returns to the saved state --- the junction point --- and continues the main stem from there. Nested brackets produce nested branches: branches that themselves have branches.

The angle delta is a free parameter that dramatically affects the output geometry. The production rule F -> F[+F]F[-F]F generates a spindly weed at delta = 25.7 degrees, a bush at delta = 20 degrees, and a geometric skeleton at delta = 90 degrees. The same grammar, the same topology of branching, produces visually distinct plants by changing one number.

Step length d can also vary. In parametric L-systems, F carries a parameter: F(l) means move forward by length l. This allows taper (segments get shorter deeper in the branch hierarchy) and allometric growth.

Deterministic, Stochastic, and Context-Sensitive

L-systems are classified by the complexity of their production rules:

D0L (deterministic, context-free). Each symbol has exactly one production rule. The same axiom always produces the same string at every generation. There is no randomness and no dependence on neighboring symbols. The Koch curve, Sierpinski triangle, and the classic plant grammars are D0L systems. This is the simplest and best-studied class.

Stochastic L-systems. A symbol may have multiple production rules, each with an assigned probability. At each derivation step, each occurrence of the symbol independently selects a rule according to the probability distribution. Two derivations from the same axiom produce different strings. The result: variation within a species. Every tree generated by a stochastic plant grammar is different, but they share the same branching logic and are recognizable as members of the same type. This is how Prusinkiewicz’s group generated realistic vegetation populations --- not one tree, but forests of individually distinct but botanically consistent trees.

Context-sensitive L-systems (1L, 2L). A symbol’s production depends on its left neighbor (1L system), right neighbor, or both (2L system). For example, the rule A < B -> C says that B is replaced by C only when its left neighbor is A. This models signaling between adjacent cells: cell B differentiates into type C only if cell A is next to it. Lindenmayer’s original 1968 paper used context-sensitive rules to model the differentiation of cells in the filamentous alga Anabaena catenula.

Parametric L-systems. Symbols carry numerical parameters: F(l, w) might represent a stem segment of length l and width w. Production rules can operate on the parameters: F(l, w) -> F(l * 0.9, w * 0.7) F(l * 0.6, w * 0.5). This allows continuous variation in segment dimensions, taper ratios, and branching angles within a single grammar. Hanan (1992) developed the formal theory of parametric L-systems.

Each extension increases expressive power at the cost of analytical tractability. D0L systems have decidable word problems and characterizable growth functions. Stochastic and context-sensitive systems are harder to analyze formally but closer to biological reality.

Depth and Self-Similarity

The recursive structure of L-system derivation produces self-similarity by construction.

Consider the production F -> F[+F]F[-F]F. At generation 0, the string is F --- a single segment. At generation 1, the single segment is replaced by a five-part branching structure. At generation 2, each F in the five-part structure is itself replaced by the five-part structure. The generation-2 string contains generation-1 structures as sub-strings, which contain generation-0 structures as sub-sub-strings.

The result is self-similar at every scale: each branch looks like a miniature version of the whole, because it was generated by the same rule. This is not an approximation of self-similarity; it is exact self-similarity at every generation up to the current one.

The string length grows exponentially. If a production rule replaces one symbol with k symbols (the branching factor), the string at generation n has approximately k^n symbols. For F -> F[+F]F[-F]F, k = 9 (counting all symbols including brackets and angle symbols) and the string at generation 5 has approximately 9^5 = 59,049 symbols.

The fractal dimension of the rendered geometry is determined by the branching factor and the scaling ratio. For a production that replaces a segment of length 1 with k copies scaled by factor r, the Hausdorff dimension is D = ln(k) / ln(1/r). The Koch curve (four copies at scale 1/3) has D = ln(4)/ln(3) approximately equal to 1.2619. The Sierpinski triangle has D = ln(3)/ln(2) approximately equal to 1.585.

For plant-like L-systems, the fractal dimension is typically between 1.5 and 2.0, depending on the branching density and the angle parameter. This matches the measured fractal dimensions of real tree branch structures (Mandelbrot, 1982), because the same recursive developmental logic applies at every growth point in both the model and the organism.

Further Reading