L-systems (Aristid Lindenmayer, 1968)

An L-system is a set of rules for rewriting a string of letters, in which every letter is replaced at the same time. The biologist Aristid Lindenmayer (1925–1989) introduced them in 1968 to describe how simple many-celled organisms grow. Read as drawing instructions, the same strings make branching plants, and the book The Algorithmic Beauty of Plants (1990), written with the computer scientist Przemysław Prusinkiewicz, showed in detail how to draw plants with them by computer.^1, 2

Rewriting in parallel

Lindenmayer published the idea in the Journal of Theoretical Biology in 1968 as "Mathematical models for cellular interaction in development".^1, 3 Rewriting rules were already in use: from the late 1950s Noam Chomsky's grammars described sentences by replacing symbols, but one at a time. In an L-system the rules "are applied in parallel and simultaneously replace all letters in a given word". The reason is biological: the rules stand for cell divisions in an organism "where many divisions may occur at the same time".²

The book's smallest example has two rules, a → ab and b → a, and starts from b:²

• b
• a
• ab
• aba
• abaab
• abaababa

The turtle

To get a picture, the string is read by a "turtle", an imaginary pen with a position and a heading, borrowed from the LOGO programming language. The letter F means draw one step forward; + and − mean turn left or right by a fixed angle. Two more symbols make branches: [ stores the turtle's position and heading, and ] returns to the last one stored, so a branch can be drawn and the turtle can go back to where it left the stem.²

The image at the top uses one rule from the book: start with F, replace every F by F[+F]F[−F]F, and turn by 25.7 degrees.² After one step there is a stem with two branches; after each further step every segment becomes a small copy of that shape.

Chance

A deterministic L-system draws the same plant every time. The book also describes stochastic L-systems, in which a letter has several possible rules and one of them is picked at random each time the letter is rewritten. In its example F has three rules, each with a probability of about one third: F[+F]F[−F]F, F[+F]F and F[−F]F. The results, the authors write, "look like different specimens of the same (albeit fictitious) plant species".²

New drawing

Beyond plants

The same method draws curves that are not plants at all. The book shows the Koch snowflake and other fractal curves as L-systems, and lists among later uses space-filling curves and the kolam patterns, an art form from southern India.² As with Truchet tiles, a few fixed rules decide the whole image. See also Generative art.