Next: Turtle Interpretation Up: Introduction Previous: Introduction

L-systems

The string rewriting mechanism in L-systems is different from that in Chomsky grammars in that the production rules are applied to the string in parallel, and they simultaneously replace all the letters in a given word. All symbols are terminals that can be interpreted. The system consists of an initial string called an axiom, and rewriting rules called productions. The first iteration starts by applying the production rules to the axiom as the current string. The successive strings are generated with the previous strings as the input, and then productions rewrite the strings.

A production consists of two strings - the predecessor and successor. When the production is applied to the string, the predecessor is compared against each symbol of the string. The successor replaces the symbol in the string if the symbol matches the predecessor.

In the process of string rewriting, we see that the string keeps growing in length, and that all the patterns of the old strings are preserved in some way. The number of times a string is rewritten is called depth or order. Simple axioms and rules produce strings with more and more complicated patterns, even complicated enough to mimic nature's growing process.

There are several types of L-systems. Context-free L-systems are the simplest and most common type of implementation available. Context-free means that only one symbol of the current string need be matched for a substitution to occur. To catch the environmental pattern around a symbol, context-sensitive L-systems are introduced. Context-sensitive L-systems are much more difficult to implement because the meaning of context-sensitive is not clearly defined. Context-free L-systems are the only special cases of the general context-sensitive L-systems.

Another kind of L-system, the stochastic model, adds randomness to the growing process. In this system there would be several rules with the same matching condition. The choice of a specific rule to apply string rewriting is determined by a probability distribution as a parameter of this set of rules. The interesting effect of a stochastic L-system is that it will produce different output every time, or in other words, that the growth is not predictable or reproducible with the same axiom and rules.

Next: Turtle Interpretation Up: Introduction Previous: Introduction

Tong Lin (tlin2@cs.umbc.edu)