Lindenmayer system

Artificial plants generated by 3D-L systems

The Lindenmayer or L systems are a mathematical formalism proposed in 1968 by the Hungarian theoretical biologist Aristid Lindenmayer as the basis of an axiomatic theory of biological development . L-systems have recently been used in computer graphics for the generation of fractals and in the realistic modeling of plants .

The essential principle of L-systems consists in the successive replacement of individual parts of a simple object using so-called production rules . These replacements can be performed recursively . L-systems belong to the so-called replacement systems .

The most popular replacement systems are those based on character strings. Noam Chomsky's work on formal grammars from the 1950s in particular met with great interest and stimulated research in theoretical computer science . In contrast to the sequential substitution rules in Chomsky's grammars, substitutions in L-systems take place in parallel, analogous to the simultaneous cell divisions in multicellular organisms , which were the impetus for the development of the L-systems.

L-systems are ideally suited to create representations of fractals. For this purpose, the character strings generated in the recursions of the L system are converted into directly executable commands of a system that realizes the turtle graphic , e.g. B. the programming language Logo .

Structure of an L-system

An L-system is a quadruple , where ${\ displaystyle G = \ left (V, S, \ omega, P \ right)}$

V contains the characters that are to be regarded as a variable.
S contains the characters that should be treated as constants. The characters from V and S form the alphabet of the L system.
ω is a word above the alphabet, which is called the starting word or axiom of the L-system.
P is a set of ordered pairs of words above the alphabet that define replacement rules. If the first word of each pair is a single letter from V and a replacement rule is known for each variable, then one speaks of a context-free L-system, otherwise of a context-sensitive one .

Context-free L systems

In order to create an L-system, a depth n is determined, i.e. i.e., replacement steps are repeated. In each replacement step, the current word ω is processed character by character and each character is replaced by the new word specified in the replacement rules. Please note that characters for which no replacement rule is defined are not replaced.

Context-free L-systems (also called 0L-systems) contain productions p, which are applied n times to an initial word ω (also called axiom). The productions assign a word to a maximum of one character without considering the context. If no rule is given for a character, identity is generally assumed to be a trivial replacement of the character by itself.

Example of systems without storage

Koch's snowflake

Kite curve

Many of the more well-known fractals, such as the Sierpinski triangle or the Koch curve , can be represented using L-systems above the alphabet . There is only one replacement rule for the symbol . Some examples are listed in the article Fractal . The Koch snowflake fractal has the starting word and the replacement rule . ${\ displaystyle V = {F}, S = {+, -}}$ ${\ displaystyle F}$ ${\ displaystyle \ omega = F - F - F}$ ${\ displaystyle F \ to F + F - F + F}$

To interpret such an L-system using turtle graphics, you need a compression factor and an angle . The path length at recursion depth is determined by means of the compression factor . The turtle has no memory and immediately executes the symbols of the alphabet as the following commands ${\ displaystyle s <1}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle s ^ {n}}$

${\ displaystyle F}$ : Movement forward by length and drawing ${\ displaystyle s ^ {n}}$
${\ displaystyle +}$ : Rotation to the left, counterclockwise, by the angle ${\ displaystyle a}$
${\ displaystyle -}$ : Rotation to the right, clockwise, by the angle ${\ displaystyle a}$

The angle and the factor should be coordinated in such a way that the length of the route and the replacement word of for the length of the route also have a common end point with the same starting point. ${\ displaystyle a}$ ${\ displaystyle s}$ ${\ displaystyle F}$ ${\ displaystyle 1}$ ${\ displaystyle F}$ ${\ displaystyle s}$

Some fractals like the kite curve require two replacement rules, as the variable part of the alphabet you choose e.g. B. and sets for this example and firmly. Both symbols are treated as in the illustration , i.e. H. as a drawing step forward. ${\ displaystyle V = \ left \ {R, L \ right \}}$ ${\ displaystyle \ omega = R}$ ${\ displaystyle P = \ left \ {(R \ to + R - L +), (L \ to -R ++ L -) \ right \}}$ ${\ displaystyle F}$

You can increase this type of addition of replacement rules at will, or you can define additional symbols with other actions:

${\ displaystyle f}$ : Movement forward by length without drawing, variable symbol, ${\ displaystyle s ^ {n}}$
${\ displaystyle |}$ : 180 degree rotation, constant symbol

Example of systems with storage

A LIFO stack for coordinate systems is introduced. Every coordinate transformation consists of a rotation, which can be parameterized by an angle, and a shift. The alphabet is expanded to include the constant symbols [ and ] , which have the following meanings:

[ : Put the current coordinate system on the stack
] : Restore the top coordinate system of the stack as the current one.

A branch that ends in emptiness can be drawn within a pair of brackets. This possibility was introduced for the representation of fractal trees.

Context-sensitive L-systems

In contrast to context-free L systems, the characters or character strings before or after the character to be replaced are also considered in productions. The context conditions are usually noted in such a way that the left context is separated from the character to be replaced by <, and the right context is separated by>.

Example: character set = {a, b}; Productions = {b <a → b, b> b → a}; ω = {baaa} (if there is a b to the left of a, the a is replaced by b. Analogously, a b becomes a if there is a b to the right.)

n = 0 → baaa

n = 1 → bbaa

n = 2 → dec

Etc.

Parametric L systems

In the context of the parametric L-systems, digits assigned to the characters are also considered in addition to individual characters. These parameters can not only be changed explicitly in the production rules, but you can also create conditional productions that only take effect when certain conditions are met, similar to the context-sensitive L-systems. Example: be a branch of length . The productions and let the branch grow and new branches emerge from a certain length (l = 10). ${\ displaystyle F (l)}$ ${\ displaystyle l}$ ${\ displaystyle F (l): l <10 \ to F (l + 1)}$ ${\ displaystyle F (l): l \ geq 10 \ to F (l + 1) F (1)}$

Pseudocode

Be . Then the following pseudocode describes the procedure of the L-System. ${\ displaystyle L = (\ Sigma, R, w_ {0})}$

1. Set up the current string

{\ displaystyle w_ {0}}

2. Repeat indefinitely:

2.1 Output current string

2.2 Put on a new string

{\ displaystyle \ varepsilon}

2.3 Repeat for each character in the current string from left to right:

{\ displaystyle c}

- If possible, choose a rule whose left side matches.

{\ displaystyle r \ in R}

{\ displaystyle c}

- If one exists, append the right side of to the end of the new string.

{\ displaystyle r}

{\ displaystyle r}

- If it doesn't exist, append to the end of the new string.

{\ displaystyle r}

{\ displaystyle c}

2.4 Make the new string the current string.

Two consecutive outputs of the pseudocode and are written as → .

{\ displaystyle w_ {i}}

{\ displaystyle w_ {i + 1}}

{\ displaystyle w_ {i}}

{\ displaystyle w_ {i + 1}}

If there exists such that → ... → holds, it is called derivable . ${\ displaystyle w_ {n}}$ ${\ displaystyle w_ {0}}$ ${\ displaystyle w_ {n}}$ ${\ displaystyle w_ {n}}$

If there is a derivable one such that for all rules from : → ... → → → → ... → , one says, converges against . ${\ displaystyle w_ {n}}$ ${\ displaystyle R}$ ${\ displaystyle w_ {0}}$ ${\ displaystyle w_ {n}}$ ${\ displaystyle w_ {n}}$ ${\ displaystyle w_ {n}}$ ${\ displaystyle w_ {n}}$ ${\ displaystyle L}$ ${\ displaystyle w_ {n}}$

literature

Henning Fernau: Iterated functions, languages and fractals . BI Wissenschaftsverlag, Mannheim et al. 1994, ISBN 3-411-17011-5 , ( aspects of complex systems 2).
Grzegorz Rozenberg, Arto Salomaa: The Mathematical Theory of L-Systems . Academic Press, New York NY et al. 1980, ISBN 0-12-597140-0 , ( Pure and Applied Mathematics 90).
Przemysław Prusinkiewicz , Aristid Lindenmayer : The Algorithmic Beauty of Plants . Springer Verlag, New York NY et al. 1990, ISBN 3-540-97297-8 , ( The virtual Laboratory ).
Elaine Rich: Automata, Computability and Complexity: Theory and Applications. Prentice Hall, Upper Saddle River (NJ) u. a. 2008, ISBN 978-0-13-228806-4 .

Web links

Commons : L system - album with pictures, videos and audio files

Math prism - Lindenmayer systems (»Iterations in replacement systems or: how toads draw plants«)
Lily: An interactive learning environment on the subject
Demo in HTML5 to generate Lindenmayer systems (English)
Lindenmayer systems (program for creating, editing and visualizing Lindenmayer systems)