Overview

L-system


Related Overviews

 

More Like This

Show all results sharing this subject:

  • Computing

GO

Show Summary Details

Quick Reference

A way of generating infinite sets of strings. L-systems are similar to grammars with the crucial difference that, whereas for grammars each step of derivation rewrites a single occurrence of a nonterminal, in an L-system all nonterminals are rewritten simultaneously. An L-system is therefore also known as a kind of parallel rewriting system. L-systems were first defined in 1968 by A. Lindenmeyer as a way of formalizing ways in which biological systems develop. They now form an important part of formal language theory.

The subject has given rise to a large number of different classes of L-systems. The simplest are the DOL systems, in which all symbols are nonterminals and each has a single production. For example, with productions

AAB

BA

one derives starting from A the sequence

A AB ABA ABAAB ABAABABA

This is called the sequence of the DOL-system, while the set of strings in the sequence is called the language. The growth-function gives the length of the ith string in the sequence; in the example this is the Fibonacci function.

Note that the productions define a homomorphism from {A,B}* to itself. A DOL-system consists therefore of an alphabet Σ, a homomorphism h on Σ*, and an initial Σ-word w. The sequence is then

w h(w) h(h(w) …

The letter D in DOL stands for deterministic, i.e. each symbol has just one production. An OL-system can have many productions for each symbol, and is thus a substitution rather than a homomorphism. Other classes are similarly indicated by the presence of various letters in the name: T means many homomorphisms (or many substitutions); E means that some symbols are terminals; P means that no symbol can be rewritten to the empty string; an integer n in place of O means context-sensitivity — the rewriting of each symbol is dependent on the n symbols immediately to the left of it in the string.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.