You are here
HomeLindenmayer system
Primary tabs
Lindenmayer system
Definition
Lindenmayer systems, or Lsystems for short, are a variant of general rewriting systems. Like a rewriting system, an Lsystem is also a language generator, 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 parallel in an Lsystem. The notion of Lsystem was introduced by plant biologist Aristid Lindenmayer when he was studying the growth development of red algae.
Formally, an Lsystem is a triple $G=(\Sigma,P,w)$, where
1. $\Sigma$ is an alphabet,
2. $w$ is a word over $\Sigma$, and
3. $P$ is a finite subset of $\Sigma\times\Sigma^{*}$ such that for every $a\in\Sigma$, there is at least one $u\in\Sigma^{*}$ such that $(a,u)\in P$.
$w$ is called the start word, or the axiom of $G$, and elements of $P$ are called productions of the Lsystem $G$, and are written $a\to u$ instead of $(a,u)$.
As stated above, an Lsystem 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 relation $\Rightarrow$ on $\Sigma^{*}$ as follows: for words $u,v\in\Sigma^{*}$,
$u\Rightarrow v$ iff either $u=a_{1}\cdots a_{n}$ and $v=v_{1}\cdots v_{n}$, where $a_{i}\to v_{i}\in P$, or $u=v$.
Now, take the transitive closure $\Rightarrow^{*}$ of $\Rightarrow$ and set
$L(G):=\{u\mid w\Rightarrow^{*}u\}.$ 
Then $L(G)$ is called the language generated by the Lsystem $G$. An Llanguage is $L(G)$ for some Lsystem $G$.
Examples
1. Let $G=(\{a\},\{a\to a^{2}\},a)$. In two derivations, we get $a\Rightarrow a^{2}\Rightarrow a^{2}a^{2}=a^{4}$. It is easy to see that after $n$ derivations, we get $a\Rightarrow^{*}a^{{2^{n}}}$, and that $L(G)=\{a^{{2^{n}}}\mid n\geq 1\}$. Note that if parallel rewriting is not required then $a^{3}$ may be derived in three steps: $a\Rightarrow a^{2}\Rightarrow(a^{2})a=a^{3}$.
2. Let $G=(\{a\},\{a\to a,a\to a^{2}\},a)$. Then $L(G)=\{a\}^{+}$.
3. Let $G=(\{a\},\{a\to\lambda,a\to a^{2}\},a)$. Then $L(G)=\{a^{{2n}}\mid n\geq 0\}\cup\{a\}$.
4. Let $G=(\{a,b\},\{a\to ab,b\to ba\},a)$. Then we get a sequence of words $a\Rightarrow ab\Rightarrow abba\Rightarrow abbabaab\Rightarrow\cdots$, and $L(G)$ is the set containing words in the sequence. Note the recursive nature of the sequence: if $u_{n}$ is the $n$th word in the sequence, then $u_{1}=a$ and $u_{{n+1}}=u_{n}h(u_{n})$, where $h$ is the homomorphism given by $h(a)=b$ and $h(b)=a$.
5. Lsystems can be used to generate graphs. Usually, symbols in $\Sigma$ represent instructions on how to construct the graph. For example,
$G=(\{a,b,c\},\{a\to a,b\to b,c\to cacbbcac\},c)$ generates the famous Koch curve. If $u\in L(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:
(a) write $u=d_{1}\cdots d_{m}$, where $d_{i}\in\Sigma$ (it is easy to see that $m=2^{{n1}}$).
(b) at each $d_{i}$, a current position $z_{i}$, and current direction $\theta_{i}$, are given.
(c) start at the origin on the Euclidean plane in the positive $x$ direction, so that $z_{0}=(0,0)$ and $\theta_{0}=0$.
(d) upon reading $d_{i}$, where $i>0$:

if $d_{i}=a$, set $z_{i}=z_{{i1}}$ and $\theta_{i}=\theta_{{i1}}+60$,

if $d_{i}=b$, set $z_{i}=z_{{i1}}$ and $\theta_{i}=\theta_{{i1}}60$,

if $d_{i}=c$, draw a line segment of unit length from $z_{{i1}}$ to a point $P$ based on $\theta_{{i1}}$, and set $z_{i}=P$ and $\theta_{i}=\theta_{{i1}}$.

A production $b\to u$ is said to correspond to $a\in\Sigma$ 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 $a\to a$. A symbol in $\Sigma$ 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.
Properties
Given an Lsystem $G=(\Sigma,P,w)$, we can associate a function $f_{G}:\Sigma\to 2^{{\Sigma^{*}}}$ as follows: for each $a\in\Sigma$, set
$f_{G}(a):=\{u\mid a\to u\in P\}.$ 
Then $f_{G}$ extends to a substitution $s_{G}:\Sigma^{*}\to 2^{{\Sigma^{*}}}$. It is easy to see that $s_{G}(w)$ is just the set of words derivable from $w$ in one step: $s_{G}(w)=\{u\mid w\Rightarrow u\}$. In fact,
$L(G)=\bigcup\{s_{G}^{n}(w)\mid n\geq 0\},$ 
where $s_{G}^{0}(w)=\{w\}$, and $s_{G}^{{n+1}}(w)=s_{G}(s_{G}^{n}(w))$.
In relation to languages described by the Chomsky hierarchy, we have the following results:
1. Every Llanguage is contextfree.
2. If an Lsystem $G=(\Sigma,P,w)$ contains a constant production for each symbol in $\Sigma$, then $L(G)$ is contextfree.
3. Denote the families of regular, contextfree, contextsensitive, and Llanguages by $\mathscr{R},\mathscr{F},\mathscr{S},\mathscr{L}$, and set $\mathscr{X}_{1}=\mathscr{R}$, $\mathscr{X}_{2}=\mathscr{F}\mathscr{R}$, and $\mathscr{X}_{2}=\mathscr{S}\mathscr{F}$. Then $\mathscr{L}\cap\mathscr{X}_{i}$ and $\overline{\mathscr{L}}\cap\mathscr{X}_{i}$ are nonempty for $i=1,2,3$. Here, $\overline{\mathscr{L}}$ is the complement of $\mathscr{L}$ in $2^{{\Sigma^{*}}}$, the family of all languages over $\Sigma$.
Subsystems
An Lsystem is said to be deterministic if every symbol in $\Sigma$ has at most one (hence exactly one) production corresponding to it. A deterministic Lsystem is also called a DLsystem. Examples 1,4,5 above are DLsystems. For a DLsystem, the associated substitution is a homomorphism, which means that for each $n\geq 0$, the set $s_{G}^{n}(w)$ is a singleton, so we get a unique sequence of words $w_{0},w_{1},\ldots$, such that $w_{n}\Rightarrow w_{{n+1}}$. If $w_{n}<w_{{n+1}}$ for some $n$, then the word sequence is infinite. In particular, if $w_{n}$ is a prefix of $w_{{n+1}}$ for all large enough $n$, and the lengths of the words have the property that $w_{n}=w_{{n+1}}$ implies $w_{m}<w_{{m+1}}$ for some $m>n$, then the DLsystem 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 ThueMorse sequence (an infinite word is an infinite sequence).
An Lsystem is said to be propagating if no productions are of the form $a\to\lambda$. A propagating Lsystem is also called a PLsystem. All examples above, except 3, are propagating. A DPLsystem is a deterministic propagating Lsystem. In a DPLsystem, the lengths of the words in the corresponding sequence are nondecreasing, and one may classify DPLsystems by how fast these lengths grow.
Variations
There are also ways one can extend the generative capacity of an Lsystem by generalizing some or all of the criteria defining an Lsystem. Below are some:
1. Create a partition of $\Sigma=N\cup T$, the set $N$ of nonterminals and the set $T$ of terminals, so that only terminal words are allowed in $L(G)$. Such a system is called an ELsystem. Formally, an ELsystem is a 4tuple
$H=(N,T,P,w)$ such that $G_{H}=(N\cup T,P,w)$ is an Lsystem, and $L(H)=L(G_{H})\cap T^{*}$.
2. Notice that the productions in an Lsystem are contextfree 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 Lsystem is also known as a 0Lsystem. We can generalize an 0Lsystem by permitting contextsensitivity in the productions. If the rewriting of a symbol depends both on its left and right neighboring symbols, the resulting system is called a 2Lsystem. On the other hand, a 1Lsystem is a system such that dependency is onesided.
Formally, a 2Lsystem is a quadruple
$(\Sigma,P,w,\sqcup).$ Both $\Sigma$ and $w$ are defined as in an Lsystem. $\sqcup$ is a symbol not in $\Sigma$, denoting a blank space. $P$ is a subset of $\Sigma_{1}\times\Sigma\times\Sigma_{1}\times\Sigma^{*}$, where $\Sigma_{1}=\Sigma\cup\{\sqcup\}$, such that for every $(a,b,c)\in\Sigma_{1}\times\Sigma\times\Sigma_{1}$, there is a $u\in\Sigma^{*}$ such that $(a,b,c,u)\in P$. Elements of $P$ are called productions, and are written $abc\to u$ instead of $(a,b,c,u)$. Rewriting works as follows: the binary relation $\Rightarrow$ on $\Sigma^{*}$ called a rewriting step, is given by $u\Rightarrow v$ iff either $u=v$, or $u=a_{1}\cdots a_{n}$ and $v=v_{1}\cdots v_{n}$, such that
(a) $\sqcup a_{1}a_{2}\to v_{1}$,
(b) $a_{{i1}}a_{i}a_{{i+1}}\to v_{i}$ where $i=2,\cdots,n1$, and
(c) $a_{{n1}}a_{n}\sqcup\to v_{n}$.
If $n=2$, then productions of the second form above do not apply. If $n=1$, then $\sqcup a_{1}\sqcup\to v_{1}$ are the only productions.
A 1Lsystem is then a 2Lsystem such that either, $abc\to u$ for some $c\in\Sigma_{1}$ implies $abd\to u$ for all $d\in\Sigma_{1}$, or $cab\to u$ for some $c\in\Sigma_{1}$ implies $dab\to u$ for all $d\in\Sigma_{1}$.
It is easy to see that an Lsystem is a 2Lsystem such that if $abc\to u$ for some $a,c\in\Sigma_{1}$, then $dbe\to u$ for all $d,e\in\Sigma_{1}$.
3. Allow the possibility that not all of the symbols may be rewritten. This means that $u\Rightarrow v$ iff either $u=v$, or $u=a_{1}\cdots a_{n}$ and $v=v_{1}\cdots v_{n}$, and either $a_{i}=v_{i}$ or $a_{i}\to v_{i}\in P$.
4. Allow more than one axiom. In other words, the single axiom word $w$ is replaced by a set $W$ of axioms.
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Mathematics Subject Classification
92C80 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections