Lindenmayer system

Definition

Lindenmayer systems, or L-systems for short, are a variant of general rewriting systems. Like a rewriting system, an L-system 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 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=(\mathrm{\Sigma },P,w)$, where

1. $\mathrm{\Sigma }$ is an alphabet,

2. $w$ is a word over $\mathrm{\Sigma }$, and

3. $P$ is a finite subset of $\mathrm{\Sigma }\times {\mathrm{\Sigma }}^{*}$ such that for every $a\in \mathrm{\Sigma }$, there is at least one $u\in {\mathrm{\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 L-system $G$, and are written $a\to u$ 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 relation $\Rightarrow$ on ${\mathrm{\Sigma }}^{*}$ as follows: for words $u,v\in {\mathrm{\Sigma }}^{*}$,

$u\Rightarrow v$ iff either $u=a_1\mathrm{\cdots }{a}_n$ and $v=v_1\mathrm{\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 L-system $G$. An L-language is $L(G)$ for some L-system $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\ge 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\ge 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 \mathrm{\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. L-systems can be used to generate graphs. Usually, symbols in $\mathrm{\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:

   1. write $u=d_1\mathrm{\cdots }{d}_m$, where $d_i\in \mathrm{\Sigma }$ (it is easy to see that $m=2^{n-1}$).

   2. at each $d_i$, a current position $z_i$, and current direction ${\theta }_i$, are given.

   3. start at the origin on the Euclidean plane in the positive $x$ direction, so that $z_0=(0,0)$ and ${\theta }_0=0$.

   4. upon reading $d_i$, where $i>0$:

      • if $d_i=a$, set $z_i=z_{i-1}$ and ${\theta }_i={\theta }_{i-1}+60$,

      • if $d_i=b$, set $z_i=z_{i-1}$ and ${\theta }_i={\theta }_{i-1}-60$,

      • if $d_i=c$, draw a line segment of unit length from $z_{i-1}$ to a point $P$ based on ${\theta }_{i-1}$, and set $z_i=P$ and ${\theta }_i={\theta }_{i-1}$.

A production $b\to u$ is said to correspond to $a\in \mathrm{\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 $\mathrm{\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 L-system $G=(\mathrm{\Sigma },P,w)$, we can associate a function $f_G:\mathrm{\Sigma }\to 2^{{\mathrm{\Sigma }}^{*}}$ as follows: for each $a\in \mathrm{\Sigma }$, set

$$f_G(a):=\{u\mid a\to u\in P\}.$$

Then $f_G$ extends to a substitution $s_G:{\mathrm{\Sigma }}^{*}\to 2^{{\mathrm{\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\ge 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 L-language is context-free.

2. If an L-system $G=(\mathrm{\Sigma },P,w)$ contains a constant production for each symbol in $\mathrm{\Sigma }$, then $L(G)$ is context-free.

3. Denote the families of regular, context-free, context-sensitive, and L-languages by $ℛ,ℱ,𝒮,ℒ$, and set ${𝒳}_1=ℛ$, ${𝒳}_2=ℱ-ℛ$, and ${𝒳}_2=𝒮-ℱ$. Then $ℒ\cap {𝒳}_i$ and $\overline{ℒ}\cap {𝒳}_i$ are non-empty for $i=1,2,3$. Here, $\overline{ℒ}$ is the complement of $ℒ$ in $2^{{\mathrm{\Sigma }}^{*}}$, the family of all languages over $\mathrm{\Sigma }$.

Subsystems

An L-system is said to be deterministic if every symbol in $\mathrm{\Sigma }$ 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 $n\ge 0$, the set $s_G^n(w)$ is a singleton, so we get a unique sequence of words $w_0,w_1,\mathrm{\dots }$, such that $w_n\Rightarrow w_{n+1}$. If 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 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\to \lambda$. 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.

Variations

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. Create a partition of $\mathrm{\Sigma }=N\cup T$, 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

   $$H=(N,T,P,w)$$

   such that $G_H=(N\cup T,P,w)$ is an L-system, and $L(H)=L(G_H)\cap T^{*}$.

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

   $$(\mathrm{\Sigma },P,w,\bigsqcup ).$$

   Both $\mathrm{\Sigma }$ and $w$ are defined as in an L-system. $\bigsqcup$ is a symbol not in $\mathrm{\Sigma }$, denoting a blank space. $P$ is a subset of ${\mathrm{\Sigma }}_1\times \mathrm{\Sigma }\times {\mathrm{\Sigma }}_1\times {\mathrm{\Sigma }}^{*}$, where ${\mathrm{\Sigma }}_1=\mathrm{\Sigma }\cup \{\bigsqcup \}$, such that for every $(a,b,c)\in {\mathrm{\Sigma }}_1\times \mathrm{\Sigma }\times {\mathrm{\Sigma }}_1$, there is a $u\in {\mathrm{\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 ${\mathrm{\Sigma }}^{*}$ called a rewriting step, is given by $u\Rightarrow v$ iff either $u=v$, or $u=a_1\mathrm{\cdots }{a}_n$ and $v=v_1\mathrm{\cdots }{v}_n$, such that

   1. $\bigsqcup a_1{a}_2\to v_1$,

   2. $a_{i-1}{a}_i{a}_{i+1}\to v_i$ where $i=2,\mathrm{\cdots },n-1$, and

   3. $a_{n-1}{a}_n\bigsqcup \to v_n$.

   If $n=2$, then productions of the second form above do not apply. If $n=1$, then $\bigsqcup a_1\bigsqcup \to v_1$ are the only productions.

   A 1L-system is then a 2L-system such that either, $abc\to u$ for some $c\in {\mathrm{\Sigma }}_1$ implies $abd\to u$ for all $d\in {\mathrm{\Sigma }}_1$, or $cab\to u$ for some $c\in {\mathrm{\Sigma }}_1$ implies $dab\to u$ for all $d\in {\mathrm{\Sigma }}_1$.

   It is easy to see that an L-system is a 2L-system such that if $abc\to u$ for some $a,c\in {\mathrm{\Sigma }}_1$, then $dbe\to u$ for all $d,e\in {\mathrm{\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\mathrm{\cdots }{a}_n$ and $v=v_1\mathrm{\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.

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