L-Systems: Growing Fractal Plants with Rewriting Rules

Terminology

Term	Definition
L-System	A parallel string rewriting system invented by Aristid Lindenmayer (1968) to model the growth of biological organisms
Axiom	The initial string (seed) from which an L-system begins its rewriting process
Production Rule	A rewriting rule that replaces a symbol with a string of symbols, applied in parallel to all symbols at each step
Turtle Graphics	An interpretation method where a virtual "turtle" moves forward, turns, and draws lines based on symbols in the L-system string
Deterministic L-System (D0L)	An L-system where each symbol has exactly one production rule, making the output fully determined by the axiom
Stochastic L-System	An L-system where each symbol may have multiple production rules, chosen probabilistically at each step
Context-Sensitive L-System	An L-system where production rules depend on the neighboring symbols, not just the symbol being replaced
Branching (Push/Pop)	The symbols `[` and `]` that save and restore the turtle's state, enabling tree-like branching structures
Self-Similarity	A property of fractals where the whole has the same structure as its parts at every scale of magnification

What & Why

In 1968, biologist Aristid Lindenmayer wanted to model how algae and plants grow. He invented a formalism now called L-systems: a set of string rewriting rules applied in parallel. Start with a seed string (the axiom), replace every symbol simultaneously according to the production rules, and repeat. After a few iterations, interpret the resulting string as drawing instructions.

The result is strikingly organic. Simple rules produce ferns, trees, flowers, and snowflakes. The key difference from traditional grammars (like Chomsky's) is parallelism: all symbols are rewritten at once, mimicking how all cells in a plant divide simultaneously rather than sequentially.

L-systems matter for several reasons:

They are the standard tool for procedural plant generation in games and film (SpeedTree, Houdini).
They produce classic fractals (Koch snowflake, Sierpinski triangle, dragon curve) from trivial rules.
They connect formal language theory to biology, showing that growth can be described as computation.
They are a gateway to parametric and stochastic extensions that model realistic botanical variation.

How It Works

The Rewriting Process

An L-system is defined by a triple $(V, \omega, P)$ :

$V$ : the alphabet of symbols
$\omega$ : the axiom (initial string)
$P$ : the set of production rules

At each derivation step, every symbol in the current string is replaced in parallel according to $P$ . Symbols without explicit rules are copied unchanged (identity production).

Example: Algae growth (Lindenmayer's original)

Alphabet: $\{A, B\}$ , Axiom: $A$ , Rules: $A \to AB$ , $B \to A$

| Step | String | | ---- | -------- | | 0 | A | | 1 | AB | | 2 | ABA | | 3 | ABAAB | | 4 | ABAABABA |

The string lengths follow the Fibonacci sequence: 1, 2, 3, 5, 8, 13, ...

Turtle Graphics Interpretation

To turn strings into pictures, assign drawing commands to symbols:

F: move forward and draw a line
+: turn right by angle $\delta$
-: turn left by angle $\delta$
[: push current position and angle onto a stack (start a branch)
]: pop position and angle from the stack (end a branch)

Example: Koch curve

Axiom: $F$ , Rule: $F \to F+F-F-F+F$ , Angle: $\delta = 90°$

After 3 iterations, this produces the classic Koch curve fractal.

Example: Fractal plant

Axiom: $X$ , Rules: $X \to F+[[X]-X]-F[-FX]+X$ , $F \to FF$ , Angle: $\delta = 25°$

Extensions

Stochastic L-systems assign probabilities to multiple rules for the same symbol, producing natural variation (no two trees look identical).

Parametric L-systems attach numeric parameters to symbols: $A(t) \to A(t+1)B(t \cdot 0.5)$ , enabling continuous growth rates and size-dependent branching.

Context-sensitive L-systems let rules depend on neighboring symbols, modeling signal propagation (e.g., hormones flowing through a plant stem).

Complexity Analysis

For an L-system with alphabet size $|V|$, axiom length $|\omega|$, and maximum production length $m$ (the longest right-hand side), after $n$ derivation steps:

Operation	Time	Space	Notes
One derivation step	$O(\|s_n\|)$	$O(\|s_{n+1}\|)$	Scan current string, build next string
String length after $n$ steps	N/A	$O(m^n \cdot \|\omega\|)$ worst case	Exponential growth if every symbol expands
Turtle interpretation	$O(\|s_n\|)$	$O(d)$ stack depth	$d$ = maximum nesting depth of brackets
Rule lookup (D0L)	$O(1)$	$O(\|V\| \cdot m)$	Hash map or array indexed by symbol

The string length grows exponentially. For the Koch curve ($F \to F+F-F-F+F$, expansion factor 5), after $n$ steps:

$|s_n| = 5^n$

For the fractal plant with $F \to FF$ (expansion factor 2 for $F$), the number of line segments roughly doubles each generation. Practical implementations typically stop at $n = 5$ to $8$ iterations.

Implementation

ALGORITHM DeriveLSystem(axiom, rules, iterations)
INPUT: axiom: string, rules: map of char -> string, iterations: integer
OUTPUT: result: string after all derivation steps

BEGIN
  current <- axiom

  FOR i FROM 1 TO iterations DO
    next <- EMPTY STRING

    FOR EACH symbol IN current DO
      IF symbol EXISTS IN rules THEN
        next <- next + rules[symbol]
      ELSE
        next <- next + symbol
      END IF
    END FOR

    current <- next
  END FOR

  RETURN current
END

ALGORITHM InterpretTurtle(lString, stepLength, angle)
INPUT: lString: string of turtle commands, stepLength: float, angle: float (degrees)
OUTPUT: segments: list of line segments [(x1,y1,x2,y2)]

BEGIN
  x <- 0.0
  y <- 0.0
  heading <- 90.0    // start pointing up
  stack <- EMPTY STACK
  segments <- EMPTY LIST

  FOR EACH symbol IN lString DO
    IF symbol = 'F' THEN
      newX <- x + stepLength * COS(heading * PI / 180)
      newY <- y + stepLength * SIN(heading * PI / 180)
      APPEND (x, y, newX, newY) TO segments
      x <- newX
      y <- newY
    ELSE IF symbol = '+' THEN
      heading <- heading + angle
    ELSE IF symbol = '-' THEN
      heading <- heading - angle
    ELSE IF symbol = '[' THEN
      PUSH (x, y, heading) ONTO stack
    ELSE IF symbol = ']' THEN
      (x, y, heading) <- POP FROM stack
    END IF
  END FOR

  RETURN segments
END

Real-World Applications

Procedural vegetation in games and film: SpeedTree and Houdini use L-system variants to generate forests, hedges, and grass for AAA games and VFX shots
Botanical research: L-systems model plant development (phyllotaxis, branching angles, growth rates) to test hypotheses about hormone signaling and resource allocation
Fractal geometry education: Koch curves, Sierpinski triangles, and dragon curves are all expressible as L-systems, making them an accessible entry point to fractal mathematics
Architecture and urban planning: Procedural building facades and city layouts use L-system-like grammars (shape grammars) to generate varied but coherent designs
Music composition: L-system strings have been mapped to musical notes and rhythms, producing self-similar compositions with fractal structure
3D printing and generative art: Artists use parametric L-systems to create organic sculptures and jewelry with biologically inspired branching patterns

Key Takeaways

L-systems are parallel string rewriting systems that model growth: all symbols are replaced simultaneously at each step
Combined with turtle graphics, they produce fractal curves, realistic plants, and branching structures from a few simple rules
String length grows exponentially ($O(m^n)$), so practical applications limit iteration depth to 5-8 steps
Extensions (stochastic, parametric, context-sensitive) add natural variation, continuous parameters, and signal propagation
L-systems bridge formal language theory and biology, and are the industry standard for procedural vegetation generation