L-system

The Lindenmayer or L- systems, it is a mathematical formalism which was proposed in 1968 by the Hungarian theoretical biologist Aristid Lindenmayer as the basis of an axiomatic theory of biological development. L recently systems were applied to CG and in the generation of fractals in the realistic modeling of plants.

The essential principle of L- systems is the gradual replacement of individual parts of a single object by means of so-called production rules. These substitutions may be carried out recursively. This includes L- systems to the so-called rewriting systems.

The best-known rewriting systems are those based on strings. Especially Noam Chomsky's work from the 1950s through formal grammars were met with great interest and fertilized the research in theoretical computer science. In contrast to the sequential replacement rules in Chomsky grammars find replacements in L- systems in parallel instead, analogous to the concurrent cell divisions in multicellular organisms, which were the impetus for the development of L- systems.

L- systems are perfectly adapted to produce images of fractals. To this end, the strings generated in the recursion of the L- system will be implemented in directly executable commands of a system which implements the turtle graphics, such as the Logo programming language.

Structure of an L- system

An L- system is a quadruple, where

• V contains the characters to be considered as a variable.
• S contains the characters to be considered as constants. The sign of V and S forming the alphabet of the L- system.
• ω is a word over the alphabet, which is called start word or axiom of the L- system.
• P is a set of pairs of words over the alphabet which define substitution rules. If the first word of each pair a single letter of V, and for each variable, a substitution rule is known, then it is called a context-free L- system, or from a context-sensitive.

Context-free L- systems

To create an L- system, a depth n is fixed, ie, there are replacement steps repeated. In any replacement step the current word is ω processed character by character and each character replaced by the new, laid down in the word replacement rules. It should be noted that characters for which no substitution rule is defined, not be replaced.

Context - free L- systems (also called 0L - systems ) contain productions p, the ω (also called axioms ) n-times applied to a word beginning. The productions organize this maximum a character without regard to the context of a word. Where there is no rule for a sign, in general, the identity is assumed to be trivial replacement of the sign by itself.

Example, for systems without memory

Many of the more well-known fractals such as the Sierpinski triangle or the Koch curve, can = { F}, S = { , -} by means of L- systems over the alphabet V are shown. There is only one replacement rule for the symbol F. The article fractal are some examples. So the Koch Schneeflockenfraktal has the start word ω = F - F - F and the replacement rule P = { (F → F F - F F) }.

For the interpretation of such L- system using turtle graphics you need a compression factor s < 1 and an angle a means of compression factor is the path length at recursion depth n as sn determined. The turtle does not have a memory and executes the symbols of the alphabet as the following commands immediately

• Q: sn forward movement to length and drawing
• : Turn to the left, counter-clockwise to the angle a
• -: Rotation to the right, in a clockwise direction by the angle a

The angle a and the factor s should be adjusted so that F with track length 1 and the replacement word from F to the track length s at the same starting point also have a common endpoint.

Some fractals like the dragon curve need two replacement rules, as the variable part of the alphabet is chosen, for example, V = {R, L} and sets for this example ω = R and P = { (R → R - L ), ( L → R L ) } fixed. Both symbols to be treated in the representation, such as F, i.e., a drawing step forward.

You can increase this type of addition of any substitution rules, or define additional symbols with other actions:

• F: move forward by length sn without drawing a variable symbol,
• |: 180 degree rotation, constant symbol

Example, for systems with memory

It introduces a LIFO stack for coordinate systems. Each coordinate transformation consists of a rotation that can be parameterized by an angle and a displacement. The alphabet is extended by the constant symbols [ and ] which have the following meaning:

• [: Put the current coordinate system on the stack from
• ]: Place the top of the stack as the current coordinate system restore.

Within a pair of parentheses so an ending in the empty branch are drawn. 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 sequences are considered before or after the characters to be replaced in the productions. The context conditions are usually notated that the left context by < is separated from the characters to be replaced, and the right context as compared with >.

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