L-system

L-system (Lindenmeyer system) 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 A → AB B → A

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.