Lindenmayer Systems: Details

Basically, a Lindenmayer system begins with a string of symbols called the axiom, and applies to the axiom a set of production rules which are used to rewrite the axiom.

For example, let the axiom of a Lindenmayer system be the string of three symbols 'peg', and let the set of production rules be the single rule: 'e=i'. This is summarized in the following table:

axiom:	peg
rules:	e = i

When the rule is applied to the axiom, each 'e' symbols in the axiom is replaced with an 'i' symbol. Thus, the axiom 'peg' becomes 'pig'. This new string 'pig' is called the first generation of the L-system since it is the result of applying the rules to the axiom one time.

The second generation of this L-system is the result of applying the rules to the first generation. Since there are no 'e' symbols in the first generation, there is nothing for the rule to replace. Thus the second generation is also the string 'pig'. This rather boring L-system is summarized below:

Boring L-System
axiom:	peg
rules:	e = i
generation 1:	pig
generation 2:	pig
generation 3:	pig

L-systems are more interesting when the rules are recursive. A recursive rule is a rule that replaces a symbol with a copy of itself plus something extra. An example of a recursive rule is 'e = eie'. The table below shows the first three generations of an L-system with this recursive rule:

Recursive L-System
axiom:	peg
rules:	e = eie
generation 1:	peieg
generation 2:	peieieieg
generation 3:	peieieieieieieieg

In the first generation, the single 'e' symbol in the axiom was replaced with 'eie' creating the string 'peieg'. Since the rule in this L-system is recursive, the first generation string has two new 'e' symbols, each of which get replaced with 'eie' in the second generation...and so it goes.

The next section summarizes the definition of an L-system more formally.

Definition of an L-System

1. A set of variables: symbols that can be replaced by production rules (see below). In the Fractal Grower software, variables can be any of the 26 lower case English letters a through z
2. A set of constants: symbols that do not get replaced. In the Fractal Grower software, the constants are any of the following symbols: !, [, ], +, -.
3. A single axiom which is a string composed of some number of variables and/or constants. The axiom is the initial state of the system.
4. A set of production rules defining the way variables can be replaced with combinations of constants and other variables. A production consists of two strings - the predecessor and the successor.

Graphic Interpretation of Strings

The most common graphical interpretation applied to L-Systems is based on turtle graphics which is the best known future of the Logo programming language. Logo was invented in 1967 by Wally Feurzeig and Seymorur Papert as a kid friendly way of teaching computer science. The turtle in turtle graphics is an on-screen cursor (or on-floor robot) which can be given drawing (or movement) instructions such as move forward by a specified distance or turn right or left by a specified angle. Traditionally the cursor in turtle graphics is represented pictorially as a turtle icon.

When applying turtle graphics to L-systems, a state of the turtle is defined as a quadruple (x, y, a, c). The Cartesian coordinates (x, y) represent the turtle's position. The angle a, called the heading, is interpreted as the direction in which the turtle is facing. The color c is interpreted as the color pen that the turtle currently has pressed to the floor so that any movement of the turtle will create a line of that color. Given the step size d and the angle increment b, the turtle can respond to symbols in an L-system string according to the following instructions:

f	Move forward (in the direction of the current heading) a distance d while drawing a line of color c. The state of the turtle changes to (x', y', a, c), where x' = x + d cos(a) and y' = y + d sin(a).
h	Same as f.
g	Same as f except no line is drawn.
!	Like the f and h symbols, the ! symbol moves the turtle forward. Unlike the f and h symbols, the distance that the ! symbol moves the turtle is a function of the symbol's age. The ! symbol is a constant, so once it is added to a string, it remains in the string for all future generations. Every NEW ! symbol moves the turtle the same distance as does every f, g, and h symbol. Every generation that a ! symbol ages, its length is divided by the value of Shrinkage. Thus, a Shrinkage value > 1 makes older ! symbols shorter, and a Shrinkage value < 1 makes older ! symbols longer. The color of the ! symbol is also a function of its age. The default color scheme causes new ! symbols to draw in light greens. Older ! symbols are drawn with darker greens and the oldest ! symbols are drawn in browns. The state of the turtle changes to (x', y', a, c), where x' = x + d/sgeneration cos(a), y' = y + d/sgeneration sin(a), and s is the shrinkage value.
+	Turn right by angle b. The next state of the turtle becomes (x', y', a+b, c).
-	Turn left by angle b. The next state of the turtle becomes (x', y', a-b, c).
[	Save the current state of the turtle by pushing it onto a stack.
]	Restore the turtle to the state of the last ] by popping the state from a stack.
a	Change the color of the turtle to color a.
b	Change the color of the turtle to color b.
c	Change the color of the turtle to color c.
d	Change the color of the turtle to color d.
e	Change the color of the turtle to color e.

All other symbols are ignored by the turtle (the turtle preserves its current state).

Some of the presets in the Fractal Grower software use other symbols such as x, y and z. While these symbols are ignored by the turtle, they are still useful in the L-system grammar for building string structures containing symbols not ignored by the turtle.

Note on color: the variables 'a' through 'e' only effect the color when the 'color f and h segments by imbedded variables' radio button is selected on the color tab of the L-System control panel. If this radio button is not selected, then the turtle ignores the 'a' through 'e' symbols, and the color of each line segment is determined by the location of each f or h in the string: f and h symbols at the beginning of the string draw red segments, in the middle of the string draw green segments, and at the end of the string draw purple segments.

Note on step length: In L-systems that do not use the '!' symbol, the step length has no effect on the appearance of drawing. This is because, all 'f' and 'h' symbols are drawn with the same step length, then the complete drawing is scaled so as to fill the drawing window. A large step size will just cause the software to scale down the final drawing more. However, when the '!' is used, then the step length has a great effect on the drawing since 'f' and 'h' symbols always move forward a distance equal to the step length whereas '!' symbols move forward a distance equal to the step length raised to the power equal to the symbol's age.

Example: Dragon Curve

The dragon curve is one such fractal, and its finite approximation can be created with an L-System:

Dragon Curve L-System
variables:	f h
constants:	+ -
axiom:	f
rules:	f = f-h h = f+h
angle increment:	90 degrees
generation 1:	f-h
generation 2:	f-h - f+h
generation 3:	f-h - f+h - f-h + f+h
generation 4:	f-h - f+h - f-h + f+h - f-h - f+h + f-h + f+h

This L-System has two rules: one for replacing 'f' symbols and one for replacing 'h' symbols. Therefore, both 'f' and 'g' are variables of the L-System. The '+' and '-' symbols are considered constants because there are no rules in the system for replacing these two symbols. The axiom of the system is a single 'f' symbol. Therefore, when creating the first generation, the rule for replacing 'h' symbols is not used.

The red and green colors in the table help make the substitution process easier to perceive. At each generation, the new symbols that result from replacing an 'f' symbol are shown in green, and the new symbols that result from replacing an 'h' symbol are shown in red. Each symbol that is more then one generation old is shown in black. Only constants can be more then one generation old, because variables are always replaced at each generation. Only some of the '+' and '-' symbols are shown in black because only these are more then one generation old.

Let's take a step by step examination of the second generation of this L-System. The generation 2 string is: 'f - h - f + h'.
Assuming that the initial heading of the turtle is upward on the screen, then the first 'f' will draw a line straight up. The '-' causes the turtle to change its heading by 90 degrees to be pointed directly to the left. The 'h' draws a line directly to the left of the screen. The second '-' symbol again turns the turtle 90 degrees to its left which is directly down on the screen. The f symbol draws a unit length line in the down direction. The last turn symbol in the string is a '+' which turns the turtle to its right by 90 degrees. However, since current heading of the turtle is pointed downward, its right is the screen's left, so again the turtle's heading is to the left of the screen. Finally, the h symbol draws a unit length line to the screen's left. The resulting image is shown is figure 1 with line segment colors matching the 'f' and 'h' colors in the description above.

figure 1