# L-systems and Sierpinski Triangle

I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below).

I'm interested to know how could one arrange the rules of an L-system so that it would converge to a to the Sierpinski triangle. What did he/she have in mind?

-
It's very nice. But doesn't example 5 on the wikipedia page to which you link provide two different L-systems that converge to the Sierpinski triangle? The meaning of the generated words is explained there. Could you clarify exactly what is the question here? – Joel David Hamkins Apr 27 '13 at 11:16
As I understand it, the question is how one could predict that an L-system converges to the Sierpinski triangle. – nvcleemp Apr 27 '13 at 13:56
@Joel. Thanks, but my question in the essence is the same as what nvcleemp stated. Suppose that I'm going to write the rules for an L-system such that it will converge to the triangle AND I'm not aware of those two L-systems mentioned in Wikipedia. How should I think about this problem? – Behzad Apr 27 '13 at 14:18
Behzad, are you asking for an explanation of how one would derive or come up with those L-systems? The generating rules express the fundamental fractal symmetries of the Sierpinski triangle. – Joel David Hamkins Apr 27 '13 at 14:22
@Joel Yes, that's my question. I searched but didn't find anything about "fundamental fractal symmetry". Would you kindly tell me where to read about it? – Behzad Apr 27 '13 at 14:45

The $L$-system described in the Wikipedia page to which you link is:

variables : A B

constants : + −

start : A

rules : (A → B−A−B), (B → A+B+A)

angle : 60°

Here, A and B both mean "draw forward", + means "turn left by angle", and − means "turn right by angle" (see turtle graphics). The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (otherwise the bases would alternate between top and bottom).

The way I think about this is that these rules express the fundamental fractal symmetry of the Sierpinski triangle, namely, the symmetry of the whole triangle with each of the three next-smaller triangles. If one images a "basic traverse" of the full main triangle to be traveling on a line segment from the bottom left to the bottom right, let us call this an A-move, for the fractal sits to our left as we make this move.

Thus, I would put two additional pictures before your four pictures, one consisting of a line segment at the bottom, and the next consisting of three movements, like half a hexagon, traversing one side each of the three next-smaller triangles.

If we consider replacing the basic A move with the moves arising from one level deeper in the fractal symmetry, then what we would do is follow that half hexagon, one edge each of the three next-smaller triangles: first going up on the left, then across to the right, then down at the right. Note that when we go up the (bottom half) of the left side of the big triangle, the corresponding triangle is on our right now, so this is a B move. But when we go across to the right, at the bottom of the top subtriangle, it is on our left, and then coming back down to the bottom right point, the third (lower-right) triangle is on our right. So we have replaced the basic A move (moving across the bottom of the full big triangle), with the moves B-A-B. Similarly, a B move would be replaced with A+B+A, with the corresponding interpretation of angle rotation (I believe it also makes sense to add an extra reorientation rotation at the start of this, but evidently this just gets canceled out.)

One could easily find other ways to make the traverse that would also express these fundamental symmetries, and arrive at different systems generating the Sierpinski triangle.

-

The space of legal configurations of the Towers of Hanoi puzzle with $n$ disks approximates Sierpinski's triangle.

There is a Hamiltonian path in the space of configurations which can be describes as forbidding both the transition $a\to b$ and undoing the previous step. This sweeps out the approximation to Sierpinski's triangle in the same way as the L-system (reflected from the one you show). As you do this for a puzzle with $n$ disks, you can ignore the smallest disk to get a similarly restricted path in the configurations of a puzzle with $n-1$ disks.

-

Once you get the grips around constructing the Hilbert curve: https://en.wikipedia.org/wiki/Hilbert_curve then this is not really all that hard to construct.

Any fractal that consists of $n$ identical, smaller copies of itself, and where the pieces are connected "start to finish", could probably be generated by a suitable l-system.

As an exercise: * The Koch kurve consists of 4 smaller copies of itself, connected in the end-points. * n-flakes: https://en.wikipedia.org/wiki/N-flake#Hexaflake etc...

-