Lindenmayer systems

A 0L system is a triplet $H=(V,P,\omega)$, where $V$ is a finite alphabet, $P$ is a set of context-free rules over $V$, and $\omega\in V^*$ is the axiom. Moreover, $P$ has to be complete, that is, for each symbol $a$ in $V$ there must be at least one rule $a\ensuremath{\rightarrow}x$ in $P$ with this letter $a$ on the left-hand side.

0L systems use parallel derivations: we say that $x$ directly derives $y$ in a 0L system $H=(V,P,\omega)$, with $x,y\in V^*$, written as $x \ensuremath{{\stackrel{\text{0L}}{\Longrightarrow}}_{H}} y$, if $x=x_1x_2\cdots x_n$, $y=y_1y_2\cdots y_n$, where $x_i\in V$, $y_i\in V^*$, and the rules $x_i\ensuremath{\rightarrow}y_i$ are in $P$ for $1\leq i \leq n$.

A T0L system is a triplet $H=(V,T,\omega)$, where $V$ is a finite alphabet, $T=\{T_1,\ldots,T_k\}$ is a finite set of tables over $V$, where each table $T_i$ for $1\leq i\leq k$ is a complete set of CF rules over $V$, and $\omega\in V^*$ is the axiom. We say that $x$ directly derives $y$ in a T0L system $H=(V,T,\omega)$, with $x,y\in V^*$, written as $x \ensuremath{{\stackrel{\text{T0L}}{\Longrightarrow}}_{H}} y$, if $x \ensuremath{{\stackrel{\text{0L}}{\Longrightarrow}}_{H_i}} y$ for some $i$ , $1\leq i\leq k$, with the 0L system $H_i=(V, T_i,\omega)$.

An ET0L system is a quadruple $H=(V,T,\omega, \Delta)$, where $\ensuremath{{{\overline{H}}}}=(V,T, \omega)$ is a T0L system, and $\emptyset\not =\Delta\subseteq V$ is a subset of $V$, the terminal alphabet. In an ET0L system $H=(V,T,\omega, \Delta)$ $x$ directly derives $y$, with $x,y\in V^*$, written as $x \ensuremath{{\stackrel{\text{ET0L}} {\Longrightarrow}}_{H}} y$, if $x \ensuremath{{\stackrel{\text{T0L}}{\Longrightarrow}}_{\ensuremath{{{\overline{H}}}}}} y$.

The transitive and reflexive closure of $\ensuremath{{\stackrel{\text{ET0L}} {\Longrightarrow}}_{H}}$ is denoted by $\ensuremath{\stackrel{ \text{ET0L} } {{\Longrightarrow}_{H}^{*}}}$. The generated language of the ET0L system $H$ (denoted by $L(H)$) is

$$L(H)=\{\;w\in {\Delta}^*\;\vert\;\omega \ensuremath{\stackrel{ \text{ET0L} } {{\Longrightarrow}_{H}^{*}}} w\;\}.$$

Thus in an ET0L system only words over a distinguished sub-alphabet are in the generated language. A language is said to be an ET0L language if there is an ET0L system generating it.

T0L and 0L systems are special cases of ET0L systems: $\Delta=V$ stands in both cases; moreover, in the case of 0L systems $T=\{T_1\}$ also holds. In an E0L system there is only one table but $\Delta$ is not necessarily equal to $V$. Therefore the above definition gives the generated language for these systems as well.