✐

✐

“46029˙CH09˙Miller” — 2008/8/11 — 7:17 — page 318 — #14

✐

✐

✐

✐

✐

✐

318 CHAPTER 9 Fractals: The Geometry of Nature

Level 1

Level 3 Level 4

Level 2

Figure 9.10 Four levels of a Koch curve

9.4.1 L-Systems

In 1968 Astrid Lindenmayer, a biologist, invented the L-system, a formal mathematical

theory designed to model the growth of biological systems. You can think of L-systems

as containing the instructions for how a simple cell can grow into a complex organism.

L-systems can be used to specify the rules for all kinds of fractals.

As it turns out, L-systems are based on a formal idea from computer science called a

grammar, which may be used for many reasons, including the speciﬁcation of programming

languages. A grammar consists of a set of symbols and one or more production rules.

These rules specify how one symbol can be replaced by one or more other symbols. A

production rule has two parts: (1) the left side, which speciﬁes a symbol, and (2) the right

side, which speciﬁes the symbols that can replace the one on the left. Let’s look at a simple

example of a grammar:

Axiom A

Rules A → B

B → AB

We can interpret this grammar as follows, beginning with the axiom, the starting point.

Axiom A is the simplest string you can produce in the grammar. You may also think of

the axiom in terms of a base case for the grammar. The rules tell us how we can construct

more complicated strings that are part of the grammar. For example, rule 1 tells us that

we can substitute the string B for A, and rule 2 tells us that we can change the string B

into the string AB.

✐

✐

“46029˙CH09˙Miller” — 2008/8/11 — 7:17 — page 319 — #15

✐

✐

✐

✐

✐

✐

9.4 Snowﬂakes, Lindenmayer, and Grammars 319

When you apply the rules to a string, you must work from left to right, applying the rule

where the left side matches the current symbol. If a rule matches, then you must apply the

rule. Let’s look at an example:

A Axiom

B (apply rule 1 to A)

AB (apply rule 2 to B)

BAB (apply rule 1 to A, then apply rule 2 to B)

ABBAB (apply rule 2 to B, then rule 1 to A, then rule 2 to B)

BABABBAB (rules applied: 1, 2, 2, 1, 2)

Try to apply the rules and produce a few more lines on your own. If you are applying the

rules correctly, you will notice that the length of each string follows the Fibonacci sequence

of numbers: 1, 1, 2, 3, 5, 8, 13, 21, ....

To make the transition from these simple L-systems to an L-system that a turtle can use

to draw pictures, consider the interpretation of the symbols used to deﬁne the L-system.

Suppose that rather than using the symbols A and B we used the symbols F, B, +, and

−. F indicates that the turtle should move forward and draw a line. B indicates the turtle

should move backward while drawing a line. The “+” symbol indicates that the turtle

should turn right and “−” indicates that the turtle should turn left.

Let’s return to the Koch curve and consider the set of steps we outlined to draw a simple

curve. We can specify the following set of actions as an L-system:

Axiom F

Rule F → F − F++F− F

Notice that the axiom gives us a straight line, which is the simplest Koch curve. But if we

apply the production rule one time, we get the string F−F++F−F. This gives us the next

simplest Koch curve. Applying the production rule to the string F−F++F−F gives us the

string F−F++F−F−F−F++F−F++F−F++F−F−F−F++F−F.

Given a string of instructions, it is straightforward to write a Python function that could

interpret the string and make the appropriate calls to turtle methods. To successfully draw

a Koch curve, we would need to know the distance to have the turtle go forward, along

with the angle for the turtle to turn.

Listing 9.5 shows the code for the function drawLS. The drawLS function simply iterates

over each character in the instruction string. When an “F”or“B” is encountered, the

turtle is instructed to move forward or backward distance units. When a “+”or“--”is

Get *Python Programming in Context* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.