“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 specification 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 specifies a symbol, and (2) the right
side, which specifies 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
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 Snowflakes, 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 define 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 FF++FF. This gives us the next
simplest Koch curve. Applying the production rule to the string FF++FF gives us the
string FF++FFFF++FF++FF++FFFF++FF.
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.