L-Systems

iconfern.gif

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:

  1. VARIABLES are symbols denoting elements that can are replaced.
  2. CONSTANTS are symbols denoting elements that remain fixed. E.g. The expression:
    constants.png
    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”.
  3. RULES (“syntax”) define how the variables are to be replaced by constants or other variables. e.g. in above example
    rules.png
    would be one such rule.
  4. START words are expressions defining how the system begins. e.g. the above examples from english might start from the single variable
    starts.png

[ Top ]

Example – Fibonacci numbers

Consider the simple grammar, defined as follows …

grammar.png

This L-system produces the following sequence of strings …

alga-patterns.png

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

fibonacci-sequence.png
[ 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

iconalga.gif

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

grammar.png

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

l-systems.png
[ Top ]

Example – Turtle Graphics

iconwalk.gif

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:

turtle-grammar.png

where

tutle-denotes.png

and the basic production rules are:

turtle-production-rules.png

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

tutle-movements.png

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.

turtle-random-walk.png
[ Top ]

Example – A compound leaf (or branch)

iconfern-1.gif

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.

leaf-model.png
[ Top ]

Exercises

  1. Using the notation for turtle geometry above, how could you produce a random walk like that shown in part (b) of the figure?
  2. Use the program FRACTINT to generate some patterns using L-systems.
  3. 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″
    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.
    2. 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”).
    3. Restart FRACTINT and look at the L-system you have just created. Compare it to the original pattern.

[ Top ]