Standard Watson-Crick E0L systems

By a similar technique as we used in the previous section, we prove that any recursively enumerable language can be generated by a standard Watson-Crick ET0L system. This will not be a deterministic system, but has only one table, that is, it is a standard Watson-Crick E0L system. We will see from the construction that the non-determinism of the system can be eliminated by splitting the set of rules into two tables, thus we will obtain another representation of recursively enumerable languages by standard Watson-Crick EDT0L systems.

Theorem 6.5  
Let $L$ be a recursively enumerable language. Then there exists a standard Watson-Crick E0L system $\Sigma$, such that $L=L(\Sigma)$.

PROOF.
The main ideas of the proof are the same as those of the previous proof: for the recursively enumerable language $L$ we take the representation given by Theorem 6.3. Starting from this, we construct a system whose working can be divided into three different phases as explained in Section 6.2.

Because in a standard Watson-Crick E0L system we have only one table, we have to use other techniques to ensure the possibility of introducing any pair $(u_i,v_i)$ in the first phase and any pair $(\lambda, z_{a_j})$ in the second one. In order to do this, we have $2m+1$ sub-alphabets for the first phase, where $m$ is the number of the pairs $(u_i,v_i)$. These alphabets are in the form of $[W,i]$ for $0\leq i\leq m$ and $[W,i,1]$ for $1\leq i\leq m$. They are used in the following way: we can modify the sentential form by introducing the pair $(u_i,v_i)$ into it only during the two steps while the sentential form is rewritten from a word over $[W,i-1]$ into a word $[W,i,1]$ and from a word over $[W,i,1]$ into a word over $[W,i]$. In this two-step period we can modify the sentential form according to the current pair $(u_i,v_i)$ or we can skip this possibility, going on without altering the sentential form. At the end of this process, that is, when the sentential form is over $[W,m]$, we can continue the first phase by rewriting the sentential form into a word over $[W,0]$ or we can finish this phase and start the second one with a word over $[W,m+1]$.

In the second phase we use the same technique: we have $2{\ell}+1$ alphabets in the form of $[W,m+t+1]$ for $0\leq t\leq l$ and $[W,m+t+1,1]$ for $1\leq t\leq {\ell}$, where ${\ell}$ is the number of $a_j$'s. We can put the pair $(\lambda, z_{a_k})$ into the sentential form during the two steps from $[W,m+k]$ to $[W,m+k+1,1]$ and from $[W,m+k+1,1]$ to $[W,m+k+1]$ or we can skip this possibility by not altering the sentential form during these two steps. At the end of this process (that is, when the sentential form is over $[W,m+{\ell}+1]$) we can continue the second phase by the pair $(\lambda, z_{a_1})$ or we can finish it by rewriting the sentential form into a word over $[W,m+{\ell}+2]$.

The last part of the derivation is analogous to the one used in the previous section: the checking is done through the alphabets $[W,m+{\ell}+2]$, $[W,m+{\ell}+3]$, $[W,m+{\ell}+4]$. Only those words $w=x_1\cdots x_n$ are generated for which there is a pair $(u_{s_1}u_{s_2}\cdots u_{s_r}, v_{s_1}v_{s_2}\cdots v_{s_r}z_{x_1}z_{x_2}\cdots z_{x_n})$ whose members are equal.

As in the previous proof, for the sake of readability, we use notations slightly different from the usual ones: the complementary symbol of $[X,i]$ is denoted by $[\ensuremath{{{\overline{X}}}},i]$ and the complementary symbol of $[X,k,1]$ is denoted by $[\ensuremath{{{\overline{X}}}},k,1].$

Let $\Sigma=(V,P,\omega,\Delta)$ be the standard Watson-Crick E0L system given as follows.

$$V=\cup_{i=0}^{m+l+4}[W,i]\cup_{k=1}^{m+l+2} [W,k,1] \cup W \cup \{K, \ensuremath{{{\overline{K}}}}\},$$

where $m$ is the number of the pairs $(u_i,v_i)$ in the representation given by Theorem 6.3 and ${\ell}$ is the cardinality of alph$(L)$, and $W=\left\{ A,B,\ensuremath{{{\overline{A}}}},\ensuremath{{{\overline{B}}}},C,D,\right.$ $\left.\ensuremath{{{\overline{C}}}},\ensuremath{{{\overline{D}}}}, S_{in}, S_{... ...ne{a_j}}}},b_j, \ensuremath{{{\overline{b_j}}}}, \;\vert\; 1\leq j\leq {\ell}\}$. The symbols $A,B$ and $a_j$ for $1\leq j\leq {\ell}$ have the same meaning as in the previous proof, the symbols $S$ coordinate the derivation, while the other symbols are necessary for using Watson-Crick complementarity.

The terminal alphabet is $\Delta=\{a_j\;\vert\;1\leq j\leq {\ell}\},$ and the axiom is $\omega=[S^0_{out},0].$

Let us note here that it will follow from the construction of $\Sigma$ that the sentential forms in any derivation are either over

$$\cup_{i=0}^{m+l+4}[W_1,i]\cup_{k=1}^{m+l+2} [W_1,k,1] \cup W_1 \cup \{K\}$$

or over

$$\cup_{i=0}^{m+l+4}[W_2,i]\cup_{k=1}^{m+l+2} [W_2,k,1] \cup W_2 \cup \{K\},$$

where

$$W_1=\left\{A,B,\ensuremath{{{\overline{C}}}},\ensuremath{{{\overl... ...ht\}\cup \{a_j, \ensuremath{{{\overline{b_j}}}},\;\vert\; 1\leq j\leq {\ell}\}$$    and $$$$

$$W_2=\left\{\ensuremath{{{\overline{A}}}},\ensuremath{{{\overline{... ...right\}\cup\{\ensuremath{{{\overline{a_j}}}},b_j\;\vert\; 1\leq j\leq {\ell}\}.$$

As it will turn out, the construction also indicates that the sentential form contains only one letter of type $S$, and this one letter is a purine. If it is an $S_{in}$, then the word is over $W_1$, otherwise the word is over $W_2$.

Due to these properties, in spite of the fact that we have only one table in the system, we can use different sets of rules. By changing $S_{in}$ and $S_{out}$ we can decide which set is to be applied.

Now we give the rules of $P$ for each alphabet, in the same order as they are used in a derivation. This means that starting from $[W,0]$, we give all the rules of $P$ which can be used for rewriting the letters in the current alphabet and a short explanation, too.

First we give the rules used in the first phase. If the sentential form is over $[W,i-1]$ for $1\leq i\leq m$, then the system has the following rules:

$[S_{in},i-1]\ensuremath{\rightarrow}[S_{in},i,1]\;\vert\;[\ensuremath{{{\overline{S_{out}}}}},i,1]$,
$[S_{out},i-1]\ensuremath{\rightarrow}[S_{out},i,1]\;\vert\;[\ensuremath{{{\overline{S_{in}}}}},i,1]$,
$[S^0_{out},i-1]\ensuremath{\rightarrow}[S^0_{out},i,1]\;\vert\;[\ensuremath{{{\overline{S_{in}}}}},i,1]$, and
$[X,i-1]\ensuremath{\rightarrow}[X,i,1]$ for the other letters $X\in W$.


In this step the system decides whether the current pair $(u_i,v_i)$ is to be introduced into the sentential form or not. Having $[S_{in},i,1]$ in the sentential form implies that the pair is to be introduced, otherwise the current pair is to be skipped. This decision can be made via Watson-Crick complementarity in the following way. In the sentential form all the purines but the symbol $S$ appear together with a pyrimidine, thus, apart from $S$, in the sentential form the number of purines and pyrimidines is equal. By rewriting $S$ to $\ensuremath{{{\overline{S}}}}$ the number of pyrimidines becomes greater than the number of purines, thus each letter transforms into its complementary, that is, the sentential form switches from $W_1$ to $W_2$, or vice versa. At the beginning of the derivation we have to distinguish the state when no pairs $(u_i,v_i)$ have been introduced yet. During this state the symbol $S$ has a superscript 0, which disappears only when the first pair has been represented in the sentential form. We can start the second phase only when the symbol $S$ does not have the superscript 0.


If the sentential form is over $[W,i,1]$ for $1\leq i\leq m$, then the system has the following rules (in the rules below $p$ and $q$ denote the lengths of $u_i$ and $v_i$, and $s$ and $t$ denote the values of $u_i$ and $v_i$): $[S_{in},i,1]\ensuremath{\rightarrow}[S_{in}{(A\ensuremath{{{\overline{C}}}})}^s{(B\ensuremath{{{\overline{D}}}})}^t,i]$, $[A,i,1]\ensuremath{\rightarrow}[{(A\ensuremath{{{\overline{C}}}})}^{3^p-1}A,i]$,
$[B,i,1]\ensuremath{\rightarrow}[{(B\ensuremath{{{\overline{D}}}})}^{3^q-1}B,i]$, and $[X,i,1]\ensuremath{\rightarrow}[X,i]$ for the other letters $X\in W$.


If at the beginning of this step the sentential form is over $[W_1,i,1]$, then the current pair $(u_i,v_i)$ is introduced by increasing the number of $A$'s and $B$'s according to $(u_i,v_i)$. Otherwise, the system does not do anything but changes the indices of the letters.


If the sentential form is over $[W,m]$, then the system has the following set of rules:

$[S_{in},m]\ensuremath{\rightarrow}[S_{in},m+1,1]\;\vert\;[\ensuremath{{{\overline{S_{out}}}}},m+1,1]$,
$[S_{out},m]\ensuremath{\rightarrow}[S_{out},m+1,1]\;\vert\;[\ensuremath{{{\overline{S_{in}}}}},m+1,1]$,
$[S^0_{out},m]\ensuremath{\rightarrow}[S^0_{out},m+1,1]$, and
$[X,m]\ensuremath{\rightarrow}[X,m+1,1]$ for the other letters $X\in W$.


Here the system decides whether to finish the first phase or to continue it. If the system makes the sentential form to be over $[W_1,m+1,1]$, then in the next step the system finishes the first phase, otherwise, when the sentential form is over $[W_2,m+1,1]$, it rewrites the sentential form into a word over $[W,0]$ and thus the first phase continues.


If the sentential form is over $[W,m+1,1]$, then the system has the following rules:

$[X,m+1,1]\ensuremath{\rightarrow}[X,m+1]$ for $X\in W_1$, $[X,m+1,1]\ensuremath{\rightarrow}[X,0]$ for $X\in W_2$.


In the second phase we have similar rules and the working of the system is the same as it was in the first phase: first the system decides whether to put the current $z_{a_k}$ and $a_k$ into the sentential form or not, then in the second step it works according to this decision.


If the sentential form is over $[W,m+k]$ for $1\leq k\leq {\ell}$, then the system has the following rules:

$[S_{in},m+k]\ensuremath{\rightarrow}[S_{in},m+k+1,1]\;\vert\;[\ensuremath{{{\overline{S_{out}}}}},m+k+1,1]$,
$[S_{out},m+k]\ensuremath{\rightarrow}[S_{out},m+k+1,1]\;\vert\; [\ensuremath{{{\overline{S_{in}}}}},m+k+1,1]$, and
$[X,m+k]\ensuremath{\rightarrow}[X,m+k+1,1]$ for the other letters $X\in W.$


If the sentential form is over $[W,m+k+1,1]$ for $1\leq k\leq {\ell}$, then the system has the following rules (in the rules below $q$ and $t$ denote the length and the value of $z_{a_k}$):

$[S_{in},m+k+1,1]\ensuremath{\rightarrow}[a_k\ensuremath{{{\overline{b_k}}}}S_{in}{(B\ensuremath{{{\overline{D}}}})}^t,m+k+1]$, $[B,m+k+1,1]\ensuremath{\rightarrow}[{(B\ensuremath{{{\overline{D}}}})}^{3^q-1}B,$ $m+k+1]$, and $[X,m+k+1,1]\ensuremath{\rightarrow}[X,m+k+1]$ for the other letters $X\in W.$


If the sentential form is over $[W_1,m+k+1]$, then the number of $B$'s is increased according to $z_{a_k}$ and $a_k$ is also introduced. Otherwise, the sentential form is not altered, except the indices.


If the sentential form is over $[W,m+{\ell}+1]$, then the system has the following rules:

$[S_{in},m+{\ell}+1]\ensuremath{\rightarrow}[S_{in},m+{\ell}+2,1]\;\vert\;[\ensuremath{{{\overline{S_{out}}}}},m+{\ell}+2,1]$,
$[S_{out},m+{\ell}+1]\ensuremath{\rightarrow}[S_{out},m+{\ell}+2,1]\;\vert\; [\ensuremath{{{\overline{S_{in}}}}},m+{\ell}+2,1]$, and
$[X,m+{\ell}+1]\ensuremath{\rightarrow}[X,m+{\ell}+2,1]$ for the other letters $X\in W.$


Here the system decides whether to finish the second phase or to continue it; this decision is done in the same way as in the first phase.


If the sentential form is over $[W,m+{\ell}+2,1]$, then the system has the following rules:

$[X,m+{\ell}+2,1]\ensuremath{\rightarrow}[X,m+{\ell}+2]$ for $X\in W_1$, $[X,m+{\ell}+2,1]\ensuremath{\rightarrow}[X,m+1]$ for $X\in W_2.$ In the third phase we check whether the two parts of the pair represented in the sentential form are equal or not. It is done in an analogous way as in the construction in Section 6.3. Therefore we give the rules without any further explanation.


If the sentential form is over $[W,m+{\ell}+2]$, then the system has the following rules:

$[A,m+{\ell}+2]\ensuremath{\rightarrow}[A,m+{\ell}+3]$, $[\ensuremath{{{\overline{C}}}},m+{\ell}+2]\ensuremath{\rightarrow}\lambda$, $[B,m+{\ell}+2]\ensuremath{\rightarrow}[\ensuremath{{{\overline{B}}}},m+{\ell}+3]$, $[\ensuremath{{{\overline{D}}}},m+{\ell}+2]\ensuremath{\rightarrow}\lambda$, $[a_j,m+{\ell}+2]\ensuremath{\rightarrow}[a_j,m+{\ell}+3]$, $[\ensuremath{{{\overline{b_j}}}},m+{\ell}+2]\ensuremath{\rightarrow}[\ensuremath{{{\overline{b_j}}}},m+{\ell}+3]$, for $1\leq j\leq {\ell}$, $[S_{in},m+{\ell}+2]\ensuremath{\rightarrow}\lambda$ and $[X,m+{\ell}+2]\ensuremath{\rightarrow}K$ for the other letters $X\in W.$


If the sentential form is over $[W,m+{\ell}+3]$, then the system has the following rules:

$[A,m+{\ell}+3]\ensuremath{\rightarrow}[\ensuremath{{{\overline{A}}}},m+{\ell}+4]$, $[\ensuremath{{{\overline{B}}}},m+{\ell}+3]\ensuremath{\rightarrow}[{B},m+{\ell}+4]$, $[a_j,m+{\ell}+3]\ensuremath{\rightarrow}[a_j,m+{\ell}+4]$, $[\ensuremath{{{\overline{b_j}}}},m+{\ell}+3]\ensuremath{\rightarrow}[\ensuremath{{{\overline{b_j}}}},m+{\ell}+4]$ for $1\leq j\leq {\ell}$, and $[X,m+{\ell}+3]\ensuremath{\rightarrow}K$ for the other letters $X\in W.$


If the sentential form is over $[W,m+{\ell}+4]$, then the system has the following rules:

$[\ensuremath{{{\overline{A}}}},m+{\ell}+4]\ensuremath{\rightarrow}\lambda$, $[{B},m+{\ell}+4]\ensuremath{\rightarrow}\lambda$, $[a_j,m+{\ell}+4]\ensuremath{\rightarrow}a_j$, $[\ensuremath{{{\overline{b_j}}}},m+{\ell}+4]\ensuremath{\rightarrow}\lambda$ for $1\leq j\leq {\ell}$, and $[X,m+{\ell}+4]\ensuremath{\rightarrow}K$ for the other letters $X\in W.$


To make the set $P$ complete, we also add the rules $X\ensuremath{\rightarrow}K$ for $X\in W\cup \{K,\ensuremath{{{\overline{K}}}}\}$. The construction guarantees that the system $\Sigma$ generates the language $L$ because of the following reasons:
1. All the words of $L$ can be generated according to the representation given by Theorem 6.3: in the first two phases the pairs $(u_i,v_i)$, the words $z_{x_k}$ and also the symbols $x_k$ are introduced into the sentential form, while in the third phase the checking deletes all non-terminal symbols.
2. Only those words can be generated which have a representation given in Theorem 6.3, because otherwise the system introduces symbols $K$, and thus the derivation is blocked.height 5pt width 5pt depth 0pt

We note that, unlike the construction presented in Section 6.3, the above proof uses Watson-Crick complementarity in the first and the second phase as well. Furthermore, non-determinism appears only in these two phases.

As mentioned above, with a slight modification of the system $\Sigma$ we can give another construction which shows that standard Watson-Crick EDT0L systems can generate all recursively enumerable languages.

Theorem 6.6  
Let $L$ be a recursively enumerable language. There exists a standard Watson-Crick EDT0L system $\Sigma$ with two tables, such that $L=L(\Sigma)$.

PROOF.
We modify the construction of the standard Watson-Crick E0L system given in the previous proof in the following way. Let us note, that the only place, where the system defined in Theorem 6.5 uses non-determinism is at the purine symbols $S$. Therefore now we construct two tables, and all the rules except the ones rewriting a purine $S$ symbol are put in both tables. The remaining rules, that is, those which rewrite a purine $S$ symbol, are split into two sub-sets, one of which is put into the first table, the other one is put into the second one.

The first sub-set contains the rules rewriting a purine $S$ to a purine; the second sub-set contains the other rules, that is, those switching a purine $S$ to a pyrimidine. Hence, the system can use the first table if it does not want to switch the sentential form into its complementary word, otherwise it uses the second table. This modification does not affect the generated language; the new system works in the same way as the system defined in Theorem 6.5. Therefore for every recursively enumerable language we can give a standard Watson-Crick EDT0L system with only two tables. height 5pt width 5pt depth 0pt

Let us note here that in this EDT0L system the number of tables is only two, but the number of non-terminals depends on $m$ and ${\ell}$, given by the EPC representation of $L$.