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=(\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 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 ${\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 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\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.
Lsystems 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:

(a)
write $u={d}_{1}\mathrm{\cdots}{d}_{m}$, where ${d}_{i}\in \mathrm{\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)
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 Lsystem $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 Llanguage is contextfree.

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

3.
Denote the families of regular^{}, contextfree, contextsensitive, and Llanguages by $\mathcal{R},\mathcal{F},\mathcal{S},\mathcal{L}$, and set ${\mathcal{X}}_{1}=\mathcal{R}$, ${\mathcal{X}}_{2}=\mathcal{F}\mathcal{R}$, and ${\mathcal{X}}_{2}=\mathcal{S}\mathcal{F}$. Then $\mathcal{L}\cap {\mathcal{X}}_{i}$ and $\overline{\mathcal{L}}\cap {\mathcal{X}}_{i}$ are nonempty for $i=1,2,3$. Here, $\overline{\mathcal{L}}$ is the complement^{} of $\mathcal{L}$ in ${2}^{{\mathrm{\Sigma}}^{*}}$, the family of all languages over $\mathrm{\Sigma}$.
Subsystems
An Lsystem is said to be deterministic^{} if every symbol in $\mathrm{\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\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 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 $\mathrm{\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
$$(\mathrm{\Sigma},P,w,\bigsqcup ).$$ Both $\mathrm{\Sigma}$ and $w$ are defined as in an Lsystem. $\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

(a)
$\bigsqcup {a}_{1}{a}_{2}\to {v}_{1}$,

(b)
${a}_{i1}{a}_{i}{a}_{i+1}\to {v}_{i}$ where $i=2,\mathrm{\cdots},n1$, and

(c)
${a}_{n1}{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 1Lsystem is then a 2Lsystem 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 Lsystem is a 2Lsystem 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}$.

(a)

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.
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Title  Lindenmayer system 
Canonical name  LindenmayerSystem 
Date of creation  20130322 18:57:31 
Last modified on  20130322 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  DLsystem 
Synonym  PLsystem 
Defines  Lsystem 
Defines  start word 
Defines  deterministic Lsystem 
Defines  propagating Lsystem 
Defines  Llanguage 
Defines  ELsystem 
Defines  2Lsystem 
Defines  1Lsystem 