Dave Computes With L-Systems

Let's begin with turtle graphics, in which a turtle can move forward (F), turn right 90 degrees (R), or turn left 90 degrees (L). Here is a simple program:

FRFF

For a turtle initially facing north, the program traces out the following path:

Now let's introduce the x operation, which does nothing at all. For example, the program Fx simply moves the turtle forward once. Now consider the following rule:

Replace x with Fx.

If we start with x, and apply the rule, we get Fx. If we apply the rule to Fx, we get FFx. After applying the rule 8 times, we get FFFFFFFFx. Therefore, this replacement rule can be used to draw an arbitrarily long straight line. We'll abbreviate this rule as x → Fx. It is our first example of a Lindenmayer System, or L-System. Here is another example:

x → FRx

Starting from x, this rule gives us FRx, then FRFRx, then FRFRFRx, then FRFRFRFRx, which will draw a square. Applying the rule any more will simply retrace the original square path. Now it's time for a more interesting rule.

x → xFxR

Starting from x, this rule gives us xFxR, then xFxRFxFxRR, then xFxRFxFxRRFxFxRFxFxRRR. But here's another way to think about it. First, execute FR, resulting in a single line segment followed by a right turn:

Applying the rule means drawing this shape (FR), then moving forward (F), then drawing a second copy of the shape (FR), and then turning right (R). Here is the resulting path (FRFFRR):

Having drawn this shape, we move forward, draw the shape again, and turn right, resulting in level 3:

Level 4:

Level 5:

Level 6:

Level 7: 

Many levels later, we get the following tentacle-like fractal:

x → xFxR

xFxR is the most interesting L-System of length 4. (RxFx, xFxL, and LxFx are all related by symmetry.) The only other interesting and distinct L-System of length 4 is FxxR, which draws a different (uglier) tentacled shape:

x → FxxR

5-character rules allow us to produce new tentacle shapes like this one:

x → xRxRF

We can also produce more complex fractals based on three copies (3 x's):

x → xxFxR

x → xRxxF

More interesting images can emerge from 6-character rules:

x → xFRxLx

x → xxRxxF

And here are some fractals resulting from longer rules (drawn with shorter segments):

x → xxRRFxR

x → xxxRRxFR

x → xRxxFLxR

x → FxxRRxFR

x → xRRxxxFRx

x → xFxLxxRxR

x → xRxxRRxRxF

L-Systems with multiple rules can produce even more complex fractals. Here's an L-system I found for drawing a version of the dragon fractal:

x → xRyF

y → FxLy

L-Systems can also use angles other than 90 degrees. This is necessary to produce Fractals like the Sierpinski curve, Koch curve, or even Penrose tilings.