Lesson 2 - String Rewriting (scroll down for directions)
In trying to imitate the structure of a real plant, we notice that there
is a lot of repetition. Also, trying to imitate a complicated real plant
using a string of symbols would be very tedious. Fortunately
Using ideas from formal language theory, Aristid Lindenmayer, a Dutch
biologist interested in the development of filamentous organisms, hit
upon the idea of generating new character strings from existing ones
by replacing given characters with strings of characters in a parallel
manner that resembles the growth of living organisms.
The idea behind parallel string rewriting systems is this: we start with
an initial character, called the axiom and a finite set of rules,
called productions, each of which assigns to a character in the
alphabet a word (that is, a string of characters) from our alphabet.
For example, suppose a production assigns to the character I the word
I[A]A(I)A, then we write:
I -> I[A]A(I)A
We call I the left side of the production and the string of
characters I[A]A(I)A the right side of the production. One of the
productions must contain the axiom as its left side. At Stage 0
the string contains just one character, the axiom. At Stage 1 the axiom is replaced
by the string on the right side of the production containing the axiom. to get to
stage 2, we start at the leftmost character in the Stage 1 string, and look at
each character in turn. If that character is the left side of one of our
productions then we replace the character in the string by the string of
characters in the right side of that production. If the character is not
the left side of any production we replace it by itself. Here is an example:
Axiom = I
Productions:
I -> I[A]I(I)
A -> A[I]B
Stage 0 string: I
Stage 1 string: I[A]I(I)
Stage 2 string: I[A]I(I)[A[I]B]I[A]I(I)(I[A]I(I))
See if you can write the Stage 3 string.
You can see how fast the strings grow. In 3 or 4 stages we have a
pretty complicated plant.
Directions for using the applet
In the applet above, the axiom is always I. You may use 1, 2, or 3
productions. The left side of one of them must be I. We have added two
more characters that represent line segments, A and B. A represents a
line segment 2/3 the length of the segment represented by I, and B a line
segent 1/3 the length of the segment represented by I. You may look at
the plant interpretation of your L-system at any stage between 0 and 7,
but notice how fast the strings grow, and for some L-systems the computer will
run out of memory. The program will warn you when this is happening.
Stage 0 will be just the axiom.
Try typing in the following L-system,
and look at the corresponding plant for stage 0, 1, 2, 3, 4.
Axiom: I
I -> I(A)A(I(A))
A -> A(I)I[A[I]]B
B -> B[L](L)BF
In the applet, the axiom is always I. For this example, enter 3 for the
number of productions, then put the Caps Lock key on and type in the
left and right sides of the productions. Enter the number of stages and
click on Draw Plant. You will have to reduce the size of the plant a
few times as you go to higher and higher stages.
Example 2
Number of productions: 3
I -> I[A]A(I)A
A -> A[I[L]IF]B
B -> A(B)B
Example 3
Here is another, a more symmetric plant:
Number of productions: 2
I -> I[I](I)AF
A -> A[I[L](L)IF]BF
Lesson 1 /
Lesson 3 /
Back to my home page