Definitions, examples

By a DNA-like alphabet we mean an alphabet of $2n$ symbols, $n\geq 1$, in the following form: $V=\{a_1,\ldots,a_n,\ensuremath{{{\overline{a_1}}}},\ldots, \ensuremath{{{\overline{a_n}}}}\}$. We say that letters $a_i$ and $\ensuremath{{{\overline{a_i}}}}$ are complementary letters and we call $V_{PUR}=\{a_1,\ldots,a_n\}$ the alphabet of purines of $V$ and $V_{\text{PYR}}=\{\ensuremath{{{\overline{a_1}}}},\ldots,\ensuremath{{{\overline{a_n}}}}\}$ is said to be the alphabet of pyrimidines of $V.$

The complementary word of a string $z$ in $V^*$ is obtained by replacing each letter in $z$ with its complementary letter and it is denoted by $\ensuremath{{{\overline{z}}}}.$ The complementary word of the empty word is itself. The morphism $h_w$, which assigns to each word $z\in V^*$ its complementary word, $\ensuremath{{{\overline{z}}}},$ is called the Watson-Crick morphism.

A standard Watson-Crick ET0L system is a construct $\Sigma=(V,T,\omega,\Delta)$ with the following properties. $V$ is a DNA-like alphabet, $T=\{T_1,\ldots,T_k\},$ $k\ge 1,$ is a finite set of tables over $V$, where each table $T_i,$ $1\leq i\leq k,$ is a complete set of context-free rules over $V$, $\omega\in V^*$ is the axiom (with ${\vert\omega\vert}_{V_{\text{PUR}}}\geq {\vert\omega\vert}_{V_{\text{PYR}}}$), and $\Delta$ is a non-empty subset of $V$, the terminal alphabet of the system.

The derivation step in a standard Watson-Crick ET0L system $\Sigma=(V,T,\omega,\Delta)$ is defined as follows. For two words, $x=x_1x_2\cdots x_n$ and $y={y_1}{y_2}\cdots {y_n}$, where $x_i\in V$, $y_i\in V^*$, $1\leq i\leq n,$ we say that $x$ directly derives $y$ in $\Sigma,$ written as $x\ensuremath{{\stackrel{\text{W-0L}}{\Longrightarrow}}_{\Sigma}}y$, if the following holds: for some $j,$ $1 \leq j\leq k,$ $x_i\ensuremath{\rightarrow}{y_i}'\in T_j$ for every $1\leq i\leq n,$ and furthermore, if ${\vert{y_1}'{y_2}'\cdots {y_n}'\vert}_{V_{\text{PUR}}}\geq {\vert{y_1}'{y_2}'\cdots {y_n}'\vert}_{V_{\text{PYR}}}$, then $y_i=y'_i$ for every $1\leq i \leq n$ and $y_i=h_w({y_i}')$ for every $1\leq i \leq n$ otherwise. In the latter case we say that a complementary transition takes place.

Thus, if in the string obtained by parallel derivation there are not more pyrimidines than purines, then the derivation continues in the usual manner, like in the case of ET0L systems. Otherwise, if the pyrimidines are in a strict majority in the word, then the derivation continues from the complementary word of the generated string.

We denote the transitive and reflexive closure of $\ensuremath{{\stackrel{\text{W-0L}}{\Longrightarrow}}_{\Sigma}}$ by ${\ensuremath{{\stackrel{\text{W-0L}}{\Longrightarrow}}_{\Sigma}}}^{*}$. The generated language consists of those words over $\Delta$ which can be obtained from the axiom in some derivation steps:

$$L(\Sigma)=\{ v\in {\Delta}^* \vert\;{\omega}{\ensuremath{{\stackrel{\text{W-0L}}{\Longrightarrow}}_{\Sigma}}}^{*}v \}.$$

If $T=\{P\}$, that is, if there is only one table, then the system is called a standard Watson-Crick E0L system. In this case we use the notation
$\Sigma=(V,P,\omega,\Delta)$, for $P$ being the unique table of the system.

If all the tables are deterministic, that is, there is exactly one rule for each letter in each table, then the system is called a standard Watson-Crick EDT0L system.

Now we present an example which illustrates the generative power of standard Watson-Crick Lindenmayer systems and shows how these systems work.

In this example we have a standard Watson-Crick E0L system and we generate the language (the same as in Example 5.10) $L(\Sigma)=\{\;{(ab^n)}^m\;\vert \; 1\leq n\leq m\;\}$, which is known not to be in ET0L (see [Rozenberg and SalomaaRozenberg and Salomaa1980]).

Example 6.1  
Let $\Sigma=(\;V,P,\omega,\Delta\;)$ be the following standard Watson-Crick E0L system:

• $V=\{S,S_1, F, E, A, B, X, X_1, X_2, a, b, \ensuremath{{{\overline{S}}}},\ensur... ...verline{X_2}}}}, \ensuremath{{{\overline{a}}}}, \ensuremath{{{\overline{b}}}}\}$,
• $P=\left\{\; S\ensuremath{\rightarrow}SF\ensuremath{{{\overline{E}}}}\;\vert\;\... ...ensuremath{{{\overline{X_1}}}} \ensuremath{{{\overline{X_1}}}}X\;\vert\;\right.$
  $\left.\hspace*{1cm}\ensuremath{{{\overline{X_1}}}}X,\; E\ensuremath{\rightarro... ...{{\overline{B}}}}\ensuremath{\rightarrow}\ensuremath{{{\overline{B}}}}, \right.$
  $\left.\hspace*{1cm} \;X_2\ensuremath{\rightarrow}X_2,\; X_1\ensuremath{\righta... ...rline{A}}}}\ensuremath{\rightarrow}a, \;{B}\ensuremath{\rightarrow}b \;\right\}$,
• $\omega=S$, and
• $\Delta=\{\;a,b\;\}$.

The form of the rules for the remaining letters of the alphabet (i.e. the ones not mentioned in $P$) is not important because these letters never occur in any derivation, but in order to have a complete table we also put the rules $Y\ensuremath{\rightarrow}Y$ into $P$, for each letter $Y\in V$ not mentioned above.

Now we explain how this standard Watson-Crick E0L system works. First the system uses the rules $S\ensuremath{\rightarrow}SF\ensuremath{{{\overline{E}}}}, F\ensuremath{\righta... ...suremath{{{\overline{E}}}}\ensuremath{\rightarrow}\ensuremath{{{\overline{E}}}}$ and derives a word in the form of $S{(F\ensuremath{{{\overline{E}}}})}^{m-1}$, where $1\leq m$. If in the next step the system uses the rule $S\ensuremath{\rightarrow}\ensuremath{{{\overline{S_1}}}}$ instead of the rule $S\ensuremath{\rightarrow}SF\ensuremath{{{\overline{E}}}}$, then there will be more pyrimidines than purines in the sentential form, thus a complementary transition takes place and we get the word $S_1{(\ensuremath{{{\overline{F}}}}{E})}^{m-1}$. Here the system has to use the rules $S_1\ensuremath{\rightarrow}\ensuremath{{{\overline{X_1}}}}A,$ $\ensuremath{{{\overline{F}}}}\ensuremath{\rightarrow}\ensuremath{{{\overline{X... ...1}}}}X\;\vert\;\ensuremath{{{\overline{X_1}}}}X,\;E\ensuremath{\rightarrow}A,\;$ and by them a word is derived which consists of one sub-word $\ensuremath{{{\overline{X_1}}}}A$, $n-1$ sub-words $\ensuremath{{{\overline{X_1}}}}XA$, and $m-n$ sub-words $\ensuremath{{{\overline{X_1}}}}\ensuremath{{{\overline{X_1}}}}XA$, where $1\leq n\leq m$. The number $n-1$ shows how many times the system used the rule $\ensuremath{{{\overline{F}}}}\ensuremath{\rightarrow}\ensuremath{{{\overline{X_1}}}}X$. The order of the sub-words is not important, so we can suppose that the word is in the form of ${(\ensuremath{{{\overline{X_1}}}}XA)}^{n-1} {(\ensuremath{{{\overline{X_1}}}}\ensuremath{{{\overline{X_1}}}}XA)}^{m-n}\ensuremath{{{\overline{X_1}}}}A$. In this word the number of purines (which is $2m-1$) exceeds the number of pyrimidines (which is $2m-n$) by $n-1\geq 0$.

In the following, the system uses the rules $\ensuremath{{{\overline{X_1}}}}\ensuremath{\rightarrow}\ensuremath{{{\overline... ...ath{\rightarrow}\ensuremath{{{\overline{B}}}}, \;X_2\ensuremath{\rightarrow}X_2$ and performs exactly $n$ steps. In each step $m-1$ new purines and $m$ new pyrimidines are generated, hence by the end of the $n$th derivation step there are more pyrimidines than purines in the sentential form. Therefore here a complementary transition takes place and we get the word ${({X_1}\ensuremath{{{\overline{X{X_2}^n{A}}}}}B^n)}^{n-1} {({X_1}{X_1}\ensuremath{{{\overline{X{X_2}^nA}}}}B^n)}^{m-n}{X_1}\ensuremath{{{\overline{A}}}}B^n$.

Here the system uses the rules $X_1\ensuremath{\rightarrow}\lambda, \ensuremath{{{\overline{X}}}}\ensuremath{\... ...emath{{{\overline{A}}}}\ensuremath{\rightarrow}a, {B}\ensuremath{\rightarrow}b$ and derives the word ${(ab^n)}^m$, where $1\leq n\leq m$.

It is clear that all the words in this form can be generated by the system (the values of the parameters $m$ and $n$ depend on the number of steps the system makes at the beginning of the derivation and on the number of positions it uses the rule $\ensuremath{{{\overline{F}}}}\ensuremath{\rightarrow}\ensuremath{{{\overline{X_1}}}}X$). It is also clear that other words cannot be generated by this system, the derivations have to follow the above line.