Lindenmayer Systems
Lindenmayer systems or L-systems, are one kind of string rewriting mechanism, consisting of a set of rules and symbols that model growth processes.
An initial string or symbol, the axiom, is defined; one or more rules are added that replace the character string in a given alphabet. In an L-system, rules are executed in parallel: per step all applicable rules are also applied to the text.
Lindenmayer defined the system this way to model the parallel development of naturally occurring phenomena in biological structures, such as in cells or shoots. A classic example in the area of cell division further elucidates the method: the development of filaments of the bacteria Anabaena Catenula and of various algae can be described using two cytological conditions a and b that represent size and readiness for division (see also [166]). After the first cell division, the subcells must grow first before they divide again. Additionally, each cell owns a polarity that describes the new position resulting from the division of the new (daughter) cells. The polarity is given by r and l and alternates in a fixed pattern during cell division. The growth and polarity of the cells can be derived using the following rule set:
{ar.. al br, al.. bl ar, br •• ar, bl •• al} •
From the axiom ar results, by application of the rules,
ar —— albr —— blarar —— alafirafir —— blarblararblarar ——
and hence the typical pattern of the filaments. The parallelism of the replace - ^ parallel replacement ment is the essential difference between the L-systems and, for example, the procedural methods. With the L-system, a variety of rule mechanisms such as the exchange of signals can be modeled, which is otherwise difficult to achieve.
An L-system is defined using a so-called formal grammar G = (V, w,P), where V represents the alphabet, w a nonterminal string (axiom), and P is a finite set of productions (replacement rules). The set V* represents the set of strings, the set V + is the set of all nonempty strings. The production p є P is written by ф ::= x, whereby ф, х є V +. In a context-free L-system (0L - system), ф has the length one; the rule is thus also applicable wherever the character a = ф appears.
Contrary to context-free L-systems in which the production rules take account only of an individual symbol, in a context sensitive L-system, a rule depends also on its neighbors, e. g., on the characters in the surrounding text. For example, ф = rav, where т, и є V + and a є V. If т has the length к and и the length l, we speak of a (k, l)-system. Often 2L-systems are used with к = l = 1 and 1L-systems with к = 1, l = 0 or к = 0,l = 1; here the context is taken into account only on one side of a.
In a deterministic L-system there exists for one ф at the most one rule with ф on the left side, e. g., for each symbol in the alphabet there is exactly one production. Thus in each case one rule can be applied. For many applications
deterministic context-free L-systems (D0L systems) are sufficient. If random processes are needed, one uses stochastic L-systems, described by the grammar G = (V, u, P, n), which, in addition to the deterministic L-system, assigns to the production set P a set of probabilities n : p ^ (0,1]. If a ф is found on the left side of one or several rules, the rule is selected from the set of the possible rules and used according to its probability.
Enumerable languages Context sensitive languages Contexfree languages Regular languages Finite Languages
ll-Systems
Figure 5.2
Power of 0L-systems and (k, l)-systems in comparison to Chomsky languages
The opposite to the parallel rule mechanisms and the otherwise customary sequential methods of Chomsky grammars is expressed in the different modeling powers of L-systems in contrast to the Chomsky languages. Modeling power represents in this context the set of denotable strings. Figure 5.2 shows the power of context-free 0L-systems and context-sensitive L-systems ((k, l)- systems) in comparison to Chomsky classes of languages.
For another example of L-systems, the alphabet V = {f, F, +, —}, the axiom
w = F--------- F------- F, and a rule set with only one rule P = {F ::= F + F —
—F + F} is provided. In this case, the rule is applied as often as F exists in the string. The derivation results in the following strings:
1. Step: F------ F------ F
2. Step: F+F — —F+F — —F+F — —F+F ——F+F — —F+F
3. Step: F + F---------- F + F + F + F F + F F + F—
—F + F + F + F---- F + F------ F + F------ F+
F + F + F----- F + F------ F + F------ F + F + F
+F——F+F——F+F——F+F+F+F——F+F
The developed pattern can now be interpreted in different ways. In the above example of the filaments, Lindenmayer uses the states of the cells in the fiber to directly produce graphic data. Alternatively a second step can be switched behind the string replacement that interprets the text, so that the geometry is generated.
Among the different methods that execute this form of graphical interpretation, the turtle metaphor [1] has gained general acceptance. It was invented by Prusinkiewicz [162]. Here a virtual turtle is moved over the drawing plane or
through a given three-dimensional space. The state of the turtle is the vector (x, y, a) that represents the position and angle of the direction in which the turtle is moving. During the movement the turtle must in each case again be aligned actively, otherwise it keeps moving in the initially chosen direction. Genuine turtles are said to move similarly: if an initial position and direction are given, they usually move in a straight line, until a change of direction becomes necessary. The movement of the computer turtle is affected completely analogously using the following four commands:
F Move turtle about d into current direction, draw a line:
(x, y, a) ^ (x + dcos a, y + dsin a, a)
f Move turtle about d into current direction, without drawing a line:
(x, y, a) ^ (x + dcos a, y + dsin a, a)
+ Increase current angle by angle S:
(x, y, a) ^ (x, y, a + S)
- Decrease current angle by angle S:
(x, y, a) ^ (x, y, a - S)
For a complete specification, the length d and the angle S still have to be defined. For d =1 and S = 60° the axiom of the L-system already described above transforms into an equilateral triangle. The application of the production rule transforms each line into a path that conforms with the generator in the von Koch curve. Accordingly, the strings in the second step produce the first “snowflake” in Fig. 5.1c and the following steps each refine the image of the curve.
