Do you remember Logo? It was a graphics program that would draw lines on the screen based on the movement of a "turtle" which acted as a pen. You would give the turtle commands like "move 2 units forward", or "turn left 10 degrees". With a little ingenuity, you would be able to create delightful designs.
L-Systems, or Lindenmayer systems, are similar. A pen moves forward and changes direction based on a sequence of commands. The most common commands are:
F     Draw a line +     Turn counter-clockwise -     Turn clockwise
So, a command sequence might be:
F+F+F+F (The red arrow marks the starting point and starting direction.)
The F's are commands to move forward, and the +'s are commands to turn left. So, if the pen is turning 90 degrees, this command sequence would draw a square. The initial command sequence is called an axiom.
L-Systems also have a set of substitution rules. So, you can replace a command in the sequence with other commands. Like this:
F -> F-F+F (The blue arrow marks the ending point and ending direction.)
Using this substitution rule on our axiom we get:
If we use the substitution rule again, we get:
As you can see, the command sequence can get complicated very quickly. This process of substitution produces complex designs and fractals.
Notice also, that the line segments got smaller each time we applied the substitution rule. While applying a reduction factor to the length of each line segment is not technically part of L-Systems, it is necessary for practical use. Otherwise, the drawn command sequence would get bigger and bigger with each refinement.
We can also have commands that move the pen without drawing anything. I denote this by preceding the draw command with an underscore. So, lets try our previous example, but change the subtitution rules a bit:
F -> _G-F+F G -> _G-_G+_G
Now, whenever it sees an underscore, the following command will move the pen, without drawing. Here's the result:
F+F+F+F _G-F+F+_G-F+F+_G-F+F+_G-F+F _G-_G+_G-_G-F+F+_G-F+F+_G-_G+_G-_G-F+F+_G-F+F+ _G-_G+_G-_G-F+F+_G-F+F+_G-_G+_G-_G-F+F+_G-F+F
Another thing we can do is introduce commands that neither move the pen nor draw, but can be replaced via a substitution rule. Consider the following L-System:
axiom: F F -> --F++F angle: 45
This produces the following:
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
Notice how the drawn L-System appears to rotate around the starting point? It rotates clockwise by 45 degrees at every refinement. We can fix that by adding a "do-nothing" command which, when replaced, will compensate for the rotation -- 45 degrees counter-clockwise for each refinement. I denote these commands with a lower-case letter.
axiom: aF F -> --F++F a -> a+ angle: 45
Now we get:
aF a+--F++F a++----F++F++--F++F a+++------F++F++--F++F++----F++F++--F++F a++++--------F++F++--F++F++----F++F++--F++F ++------F++F++--F++F++----F++F++--F++F
The commands so far allow us to create some great looking graphics, but we still have another very powerful command to introduce: brackets. The [ and ] commands allow us to save our current position and direction, and then go back to it later on. [ saves, and ] restores. Consider this:
axiom: F F -> F[-F]F[+F]F angle: 90
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
It may help to think of the sequences of commands inside a pair of brackets as a branch off of a trunk... the [ starts the branch, and the ] ends the branch and returns to where the branch started, to resume drawing the trunk.
So that's L-Systems. If you're hungry for more, read about L-Systems on Wikipedia.
Or you can play with L-Systems yourself using our applet.