Lindenmayer system


Lindenmayer systems, or L-systems for short, are a variant of general rewriting systems. Like a rewriting system, an L-system is also a languagePlanetmathPlanetmath generatorPlanetmathPlanetmathPlanetmath, where words are generated by applications of finite numbers of rewriting steps to some initial word given in advance. However, unlike a rewriting system, rewriting occurs in parallelMathworldPlanetmathPlanetmath in an L-system. The notion of L-system was introduced by plant biologist Aristid Lindenmayer when he was studying the growth development of red algae.

Formally, an L-system is a triple G=(Σ,P,w), where

  1. 1.

    Σ is an alphabet,

  2. 2.

    w is a word over Σ, and

  3. 3.

    P is a finite subset of Σ×Σ* such that for every aΣ, there is at least one uΣ* such that (a,u)P.

w is called the start word, or the axiom of G, and elements of P are called productions of the L-system G, and are written au instead of (a,u).

As stated above, an L-system is a language generator, where words are generated from the axiom w by repeated applications of productions of P. Let us see how this is done. Define a binary relationMathworldPlanetmath on Σ* as follows: for words u,vΣ*,

uv iff either u=a1an and v=v1vn, where aiviP, or u=v.

Now, take the transitive closureMathworldPlanetmathPlanetmath * of and set


Then L(G) is called the language generated by the L-system G. An L-language is L(G) for some L-system G.


  1. 1.

    Let G=({a},{aa2},a). In two derivations, we get aa2a2a2=a4. It is easy to see that after n derivations, we get a*a2n, and that L(G)={a2nn1}. Note that if parallel rewriting is not required then a3 may be derived in three steps: aa2(a2)a=a3.

  2. 2.

    Let G=({a},{aa,aa2},a). Then L(G)={a}+.

  3. 3.

    Let G=({a},{aλ,aa2},a). Then L(G)={a2nn0}{a}.

  4. 4.

    Let G=({a,b},{aab,bba},a). Then we get a sequence of words aababbaabbabaab, and L(G) is the set containing words in the sequence. Note the recursive nature of the sequence: if un is the nth word in the sequence, then u1=a and un+1=unh(un), where h is the homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath given by h(a)=b and h(b)=a.

  5. 5.

    L-systems can be used to generate graphs. Usually, symbols in Σ represent instructions on how to construct the graph. For example,


    generates the famous Koch curve. If uL(G) is derived from c in n steps, then u represents the n-th iteration of the Koch curve. To draw the n-th iteration based on u, we do the following:

    1. (a)

      write u=d1dm, where diΣ (it is easy to see that m=2n-1).

    2. (b)

      at each di, a current position zi, and current direction θi, are given.

    3. (c)

      start at the origin on the Euclidean planeMathworldPlanetmath in the positive x direction, so that z0=(0,0) and θ0=0.

    4. (d)

      upon reading di, where i>0:

      • *

        if di=a, set zi=zi-1 and θi=θi-1+60,

      • *

        if di=b, set zi=zi-1 and θi=θi-1-60,

      • *

        if di=c, draw a line segmentMathworldPlanetmath of unit length from zi-1 to a point P based on θi-1, and set zi=P and θi=θi-1.

A production bu is said to correspond to aΣ if b=a. Both productions in Example 2 correspond to a. A production is said to be a constant production if it has the form aa. A symbol in Σ is called a constant if the only corresponding production is the constant production. In the last example above, a,b are both constants. a is not a constant in Example 2, even though it has a corresponding constant production.


Given an L-system G=(Σ,P,w), we can associate a function fG:Σ2Σ* as follows: for each aΣ, set


Then fG extends to a substitution sG:Σ*2Σ*. It is easy to see that sG(w) is just the set of words derivable from w in one step: sG(w)={uwu}. In fact,


where sG0(w)={w}, and sGn+1(w)=sG(sGn(w)).

In relation to languages described by the Chomsky hierarchy, we have the following results:

  1. 1.

    Every L-language is context-free.

  2. 2.

    If an L-system G=(Σ,P,w) contains a constant production for each symbol in Σ, then L(G) is context-free.

  3. 3.

    Denote the families of regularPlanetmathPlanetmathPlanetmathPlanetmath, context-free, context-sensitive, and L-languages by ,,𝒮,, and set 𝒳1=, 𝒳2=-, and 𝒳2=𝒮-. Then 𝒳i and ¯𝒳i are non-empty for i=1,2,3. Here, ¯ is the complementMathworldPlanetmath of in 2Σ*, the family of all languages over Σ.


An L-system is said to be deterministicMathworldPlanetmath if every symbol in Σ has at most one (hence exactly one) production corresponding to it. A deterministic L-system is also called a DL-system. Examples 1,4,5 above are DL-systems. For a DL-system, the associated substitution is a homomorphism, which means that for each n0, the set sGn(w) is a singleton, so we get a unique sequence of words w0,w1,, such that wnwn+1. If |wn|<|wn+1| for some n, then the word sequence is infiniteMathworldPlanetmath. In particular, if wn is a prefix of wn+1 for all large enough n, and the lengths of the words have the property that |wn|=|wn+1| implies |wm|<|wm+1| for some m>n, then the DL-system defines a unique infinite word (by taking the union of all finite words). In Example 4 above, the infinite word we obtain is the famous Thue-Morse sequence (an infinite word is an infinite sequence).

An L-system is said to be propagating if no productions are of the form aλ. A propagating L-system is also called a PL-system. All examples above, except 3, are propagating. A DPL-system is a deterministic propagating L-system. In a DPL-system, the lengths of the words in the corresponding sequence are non-decreasing, and one may classify DPL-systems by how fast these lengths grow.


There are also ways one can extend the generative capacity of an L-system by generalizing some or all of the criteria defining an L-system. Below are some:

  1. 1.

    Create a partition of Σ=NT, the set N of non-terminals and the set T of terminals, so that only terminal words are allowed in L(G). Such a system is called an EL-system. Formally, an EL-system is a 4-tuple


    such that GH=(NT,P,w) is an L-system, and L(H)=L(GH)T*.

  2. 2.

    Notice that the productions in an L-system are context-free in the sense that during a rewriting step, the rewriting of a symbol does not depend on the “context” of the symbol (its neighboring symbols). This is the reason why an L-system is also known as a 0L-system. We can generalize an 0L-system by permitting context-sensitivity in the productions. If the rewriting of a symbol depends both on its left and right neighboring symbols, the resulting system is called a 2L-system. On the other hand, a 1L-system is a system such that dependency is one-sided.

    Formally, a 2L-system is a quadruple


    Both Σ and w are defined as in an L-system. is a symbol not in Σ, denoting a blank space. P is a subset of Σ1×Σ×Σ1×Σ*, where Σ1=Σ{}, such that for every (a,b,c)Σ1×Σ×Σ1, there is a uΣ* such that (a,b,c,u)P. Elements of P are called productions, and are written abcu instead of (a,b,c,u). Rewriting works as follows: the binary relation on Σ* called a rewriting step, is given by uv iff either u=v, or u=a1an and v=v1vn, such that

    1. (a)


    2. (b)

      ai-1aiai+1vi where i=2,,n-1, and

    3. (c)


    If n=2, then productions of the second form above do not apply. If n=1, then a1v1 are the only productions.

    A 1L-system is then a 2L-system such that either, abcu for some cΣ1 implies abdu for all dΣ1, or cabu for some cΣ1 implies dabu for all dΣ1.

    It is easy to see that an L-system is a 2L-system such that if abcu for some a,cΣ1, then dbeu for all d,eΣ1.

  3. 3.

    Allow the possibility that not all of the symbols may be rewritten. This means that uv iff either u=v, or u=a1an and v=v1vn, and either ai=vi or aiviP.

  4. 4.

    Allow more than one axiom. In other words, the single axiom word w is replaced by a set W of axioms.


Title Lindenmayer system
Canonical name LindenmayerSystem
Date of creation 2013-03-22 18:57:31
Last modified on 2013-03-22 18:57:31
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 11
Author CWoo (3771)
Entry type Definition
Classification msc 92C80
Classification msc 68Q45
Synonym L system
Synonym DL-system
Synonym PL-system
Defines L-system
Defines start word
Defines deterministic L-system
Defines propagating L-system
Defines L-language
Defines EL-system
Defines 2L-system
Defines 1L-system