The Koch Curve Via Grammar Re-Writing

Fractals have the property that at any level of magnification they are jaggy and bent. Most objects in the natural world are fractal-like because of this property. For example no matter how close one gets to a cloud, it always looks fuzzy and vaporous. It never looks like the surface of a sphere.

To geometrically specify a fractal we need a procedure that can encapsulate the complexity of the fractal at every level of magnification. There are several ways to do this. One way is by a recursive procedure that defines the shape of a fractal in terms of the shapes of its sub-parts. In the Examples section of these Help pages there is an example of creating the Koch curve that is recursive in nature (it uses the looping capability of the Recorder window). Look here for this example.

Another way to represent the recursive nature of a fractal is by the use of a ``grammar'' in which symbols represent geometric operations like movement, drawing, etc. In this grammar a set of symbols will define the overall shape of the fractal and there will be rules for how the shape of the fractal changes as we magnify sections. These rules will be called ``production'' rules as they tell us how to produce a fractal.

We will use the notion of a grammar to construct approximations of fractals. We can only construct approximations since a fractal is by its nature an infinitely complex object, at all levels, and a finite computer cannot create an infinitely complex object.

We will use the following set of symbols to control a turtle that will draw out a specific fractal, the Koch Curve. These symbols correspond to the basic turtle movements found in the Turtle Controller window.
 

This set of symbols is used in the classic work by Prusinkiewicz and Lindenmayer on grammar-based fractal systems in nature titled The Algorithmic Beauty of Plants. This beautiful book describes how one can use grammars to model plants and plant growth, as well as more abstract fractal shapes like Koch's Curve. This method of describing fractal shapes has been called "Lindenmayer Systems'' or "L-Systems'' for short.

To illustrate how to use this grammar-based fractal description system, let us look at constructing the Koch Curve using turtle geometry and the control symbols listed above.

The Koch curve is a fractal that is constructed as follows: begin with an initial segment. Replace that segment with a template curve made up of four segments as shown below. The angles inside the peak are all 60 degrees, making the triangle formed by the peak an equilateral triangle. The initial segment will be called the Koch curve at level 0. The template will be the Koch curve at level 1. If we replace each of the segments in the template with a copy of the template at a reduced scale we get the third curve -- the Koch curve at level 2.

To model the Koch curve using our set of symbols, we could say that the initial segment is basically a turtle Draw Forward, or an "F'', starting with the turtle at the bottom endpoint of the segment. The template figure is (forgetting for now the problem of scaling) a Draw Forward followed by a Turn Left of 60 degrees, then a Draw Forward followed by two Turn Rights of 60 degrees, then a Draw Forward followed by a Turn Left of 60 degrees, and finally another Draw Forward. Thus, the sentence that describes the template is: "F+F--F+F''. (Assuming our turns are always 60  degrees). Study the template curve and convince yourself that this is the correct sentence for the curve.

Thus, the Koch curve is grammatically defined by an initial sentence "F'', which we will call the axiom and a template sentence "F+F--F+F'' which governs how the initial segment is replaced to produce the template. This template sentence we will call a production rule. At level 0 then, the Koch curve is just ``F''.  At level 1 we replace "F'' by "F+F--F+F''. At level 2 we need to replace all segments by the template again. This is equivalent to replacing all occurrences of the symbol "F'' in the level 1 sentence "F+F--F+F'' by the production rule sentence "F+F--F+F''. If we do this we get a level 2 sentence of "F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F''. (Convince yourself this is right).

In other words each succeeding level of the Koch curve is represented by re-writing the sentence for the current level by using the production rule. The sentence for level 3 would be
"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--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 Koch Curve can then be completely defined by just two sentences: the starter axiom of "F'' and the production rule of "F+F--F+F''. The Koch Curve is then the curve you get by carrying out the re-writing of the axiom to an infinite level, having the turtle do the geometry.

A major difference between this grammar re-writing system of describing the Koch curve and the recursive description given in the examples is that in the grammar-based system we do not re-scale the template, whereas in the recording we shrink everything by a factor of 1/3 before looping. Thus, when the turtle draws succeeding levels of the sentence the curve will get longer and longer.  Let's look at how all of this works in practice:

First, we need to create a turtle to interpret sentence symbols. Define a vector ED and a 60 degree angle BAC as shown below (if you need help with this refer back to the main page on Turtle Geometry).  Create a point F and a turtle at F.

When you create the turtle at F, the Turtle Controller window will also pop up. We will make use of the section labeled "Grammar Turtle''. In the box labeled "Axiom:'' type F for our axiom. Then in the area labeled "Productions:'' type in the production rule in the form  F=F+F--F+F .  We use the equal sign to designate that the symbols on the left side of "='' will get replaced by the symbols on the right side.  In the box labeled "Rewrite Level:'' we can put in the level of re-writing we desire. Once we have specified this and hit return, the re-writing will take place. Note that nothing will happen with the turtle however. In the example shown we have re-written the sentence to level 3.  Note that the rewritten axiom text box now has too much text to display. To see the rest of the new sentence, just scroll down in this text area.

turtle control panel

Now we are ready to have the turtle carry out the drawing for us. If we hit the "Turtle Interpret'' button whatever is in the "Rewritten Axiom:'' text area will be interpreted and drawn to the Canvas by the turtle. However, the turtle will take quite some time to carry out the level 3 sentence (anywhere from a few seconds to several minutes, depending on the speed of your computer). If you do not want to wait that long, change the rewrite level to 2, hit return on the keyboard to rewrite the sentence to level 2 and then hit the "Turtle Interpret" button. The turtle will carry out the instructions encoded in the sentence. You might also notice that the turtle leaves the visible part of the Canvas, as shown in the figure below.

To bring the turtle back in view we just need to move point E closer to D, thus shrinking the turtle's move forward length.

At any point as the turtle carries out the interpretation of the sentence we can stop the turtle by just hitting the "Stop Turtle'' button.

This grammar re-writing system can be very powerful in representing complex fractal shapes.