## L-Systems

L-systems are sets of rules and symbols (also known as “formal grammars”) that model growth processes. The name “L-system” is short for “Lindenmayer System”, after Aristid Lindenmayer, who was one of the first people to use syntactic methods to model growth. A simple L-system contains four elements:

- VARIABLES are symbols denoting elements that can are replaced.
- CONSTANTS are symbols denoting elements that remain fixed. E.g. The expression:

Consists of grammatical variables. Each variable may replaced by constants (english words or phrases) to produce sentences in english, such as “The cat sat on the mat” or “The dog ate the bone”. - RULES (“syntax”) define how the variables are to be replaced by constants or other variables. e.g. in above example

would be one such rule. - START words are expressions defining how the system begins. e.g. the above examples from english might start from the single variable

[ Top ]

## Example – Fibonacci numbers

Consider the simple grammar, defined as follows …

This L-system produces the following sequence of strings …

If we count the length of each string, we obtain the famous Fibonacci sequence of numbers:

[ Top ]

## Applications

The power of L-systems comes when we assign meaning to the symbols and rules. For instance the symbols might represent branches of a growing tree and the rules denote the

### Example – Alga growth

The power of L-systems comes when we assign meaning to the symbols and rules. The figure shows the pattern of cell lineages found in the alga Chaetomorpha linum. To describe this pattern, we must let the symbols denote cells in different states, rather than different structures. This growth process can be generated from an axiom Aand growth rules

Here is the pattern generated by this model. It matches the arrangement of cells in the original alga.

[ Top ]

### Example – Turtle Graphics

To use L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen. For example, the program FRACTINT uses “Turtle Graphics” to produce screen images. It interprets each constant in an L-system model as a turtle command. **Turtle geometry**, invented by Seymour Papert, deals with patterns produced by the path of an imaginary turtle moving around on a plane. The path of a turtle can be described by a sequence of symbols representing the moves that the turtle makes as it moves around. These sequences form words in a formal language, defined by a grammar such as the following:

where

and the basic production rules are:

In this grammar, the variable Path denotes the (as yet) unspecified part of the turtle’s trail. The transitions represent moves made by the turtle. At any time, the completed portion of the turtle’s path is specified by a sequence of individual movements, such as

Turtle geometry is frequently used in computer graphics. Models that form complex patterns are obtained by augmenting the above grammar with new variables to denote particular pattern elements, and with new rules governing the structure of those patterns elements, hence the list of variables in the above definition is left open ended. For example, the following rules use the variables Design ,Arm ,etc to describe the formation of the simple design shown in the Figure (a). Part (b) of the figure shows a random walk.

[ Top ]

### Example – A compound leaf (or branch)

Below is a model (as used by FRACTINT) to draw a leaf (Fig. 3). A semi-colon indicates that the rest of a line is a comment.

[ Top ]

## Exercises

- Using the notation for turtle geometry above, how could you produce a random walk like that shown in part (b) of the figure?
- Use the program FRACTINT to generate some patterns using L-systems.
- Exit from FRACTINT and create a new file of L-system patterns by copying the file fractint.l as follows: “copy fractin.1 test.1″
- Use a text editor to look at the file “test.l”. This file contains the L-system definitions used by FRACTINT to draw patterns. Look at the codes provided for some of the patterns you have just drawn.
- Use the text editor to change the code of the above leaf pattern. It is a good idea to make these changes to a copy the original code and to give it a new name (e.g. “Leaf1b”).
- Restart FRACTINT and look at the L-system you have just created. Compare it to the original pattern.

[ Top ]