L-system

An L-system, or Lindenmayer system, is a parallel rewriting system and a type of formal grammar. It consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial "axiom" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures.

L-systems were originally conceived in 1968 by Aristid Lindenmayer as a mathematical description of plant development, and have since found applications in modelling various biological systems and generating realistic computer graphics, particularly for rendering plants and fractal-like structures. The key idea is to start with a simple initial state (the axiom) and apply the production rules iteratively and simultaneously to all symbols in the current string. This process generates a sequence of ever-longer strings, which can then be interpreted geometrically.

L-systems come in several variants. Deterministic, context-free L-systems (DOL-systems) are the simplest, where each symbol has exactly one production rule and the rule application does not depend on neighboring symbols. More complex L-systems allow for multiple production rules for a single symbol (stochastic L-systems) or rules that depend on the symbols to the left and right of the symbol being rewritten (context-sensitive L-systems).

The power of L-systems lies in their ability to generate complex and highly structured patterns from a small set of simple rules. By carefully designing the alphabet, axiom, and production rules, one can create strings that, when interpreted geometrically, produce intricate and visually appealing patterns reminiscent of natural structures.

While primarily used for generating static structures, L-systems can also be extended to model dynamic systems by incorporating time-dependent rules or parameters that change with each iteration. This allows for simulating the growth and development of biological organisms over time. The parallel and iterative nature of L-systems also makes them well-suited for implementation on parallel computing architectures.