Standard Watson-Crick EDT0L systems

Now we present the construction by which we can give for any recursively enumerable language a generating standard Watson-Crick EDT0L system, where the number of non-terminals is bounded by a constant.

Theorem 6.4  
Let $L$ be a recursively enumerable language. Then there exists a standard Watson-Crick EDT0L system $\Sigma$, such that $L=L(\Sigma)$. Moreover, the number of non-terminals of $\Sigma$ is bounded by a constant.

PROOF.
Let $L$ be a recursively enumerable language over an alphabet $\Delta=\{a_1,\ldots, a_l\}.$ Then, according to Theorem 6.3, there exists an EPC instance $P= (\{(u_1,v_1),$ $\ldots,$ $(u_m,v_m)\}, (z_{a_1},\ldots,z_{a_l}))$, where $1\leq m$, and $u_i,v_i,z_{a_j}\in \{1,2\}^*$ for $1\leq i\leq m$ and $1\leq j\leq {\ell}$, such that $L(P)=L$ holds.

Now we define the simulating standard Watson-Crick EDT0L system $\Sigma=(V,{T}, \omega,\Delta\cup \ensuremath{{{\overline{\Delta}}}})$, and explain its functioning. For the sake of readability, we use a notation for complementary symbols slightly different from the usual one: the complementary symbol of $[X,i]$ is denoted by $[\ensuremath{{{\overline{X}}}},i].$

The alphabet $V$ of the system $\Sigma$ is the following:

$$V=\{[S,0],[\ensuremath{{{\overline{S}}}},0]\}\cup [W,1]\cup [W,2]... ...remath{{{\overline{K}}}}\} \cup \Delta \cup \ensuremath{{{\overline{\Delta}}}},$$

where $W=\{A,B,\ensuremath{{{\overline{A}}}},\ensuremath{{{\overline{B}}}}, S, \ensuremath{{{\overline{S}}}}\;\},\;\Delta=\{a_j\;\vert\;1\leq j\leq l\},$    and $\ensuremath{{{\overline{\Delta}}}}=\{\ensuremath{{{\overline{a}}}}_j\;\vert\;1\leq j\leq {\ell}\}.$ Symbols $A$ and $B$ have the role explained in Section 6.2; symbols $S$ are used to start the derivation and to introduce the letters $a_j$; the barred letters, the pyrimidines, play role only in the checking phase.

The axiom is $\omega=[S,0].$

The set of the tables is

$$\mathcal{T}=\left\{T_{i,0}, T_{i,1},\;\vert\;1\leq i\leq m\;\righ... ...\{\; T_{k, 2}, \;\vert\; 1\leq k\leq \ell \right\}\cup\{\;T_2,T_3, T_4,T_5\;\}.$$

There are two tables corresponding to each pair $(u_i,v_i)$ for $1\leq i\leq m$ ($T_{i,0}$ and $T_{i,1}$), and there is a table corresponding to each word $z_{a_k}$ for $1\leq k\leq \ell$ ($T_{k,2}$). Tables $T_2,T_3,T_4$ and $T_5$ are used in switching from one phase to another and in finishing the derivation of the terminal words.

The tables contain the following rules and are used in the following way. All the symbols which are not mentioned in a table are rewritten into $K$, these rules make the tables complete. For $1\leq i\leq m$, let

$$T_{i,0}=\left\{[S,0]\ensuremath{\rightarrow}[S,1]{[A,1]}^s{[B,1]}^t\right\}$$

where $s$ and $t$ are the values of $u_i$ and $v_i$ according to the base three notation. (Actually, $s$ and $t$, as well as $p$ and $q$ introduced below, depend on $i$. We have disregarded the matter in our notation, to improve readability.) One of these tables is used to start the derivation and to introduce $A$'s and $B$'s into the sentential form according to the corresponding pair $(u_i,v_i)$. To start with, we have to use one of these tables $T_{i,0}$, thus it is ensured that at least one pair $(u_i,v_i)$ will be represented in the sentential form.

For $1\leq i\leq m$, let

$$T_{i,1}=\left\{[S,1]\ensuremath{\rightarrow}[S,1]{[A,1]}^s{[B,1]}... ...\rightarrow}{[A,1]}^{3^p}, [B,1]\ensuremath{\rightarrow}{[B,1]}^{3^q}\right\}$$

where $s$ and $t$ are the values, and $p$ and $q$ are the lengths of $u_i$ and $v_i$. Using one of these tables, we can modify the sentential form in such a way that it reflects the act of concatenating the pair $(u_i,v_i)$ at the end of the pair of words obtained so far. By this concatenation, the values $t_1,t_2$ of the previously obtained words become $3^p\cdot t_1+s$ and $3^q\cdot t_2+t$, respectively. Using these tables several times, by the end of the first phase of the derivation we obtain a sentential form representing a pair $(u_{s_1}\cdots u_{s_r}, v_{s_1}\cdots v_{s_r})$ with $r\geq 1$.

Let

$$T_2=\left\{[A,1]\ensuremath{\rightarrow}[A,2], [B,1]\ensuremath{\rightarrow}[B,2], [S,1]\ensuremath{\rightarrow}[S,2]\right\}.$$

This table switches a word with letters from $[W,1]$ to the corresponding word with letters from $[W,2]$.

For $1\leq k\leq {\ell}$, let

$T_{k,2}=$	$\{[S,2]\ensuremath{\rightarrow}a_k[S,2]{[B,2]}^t, [A,2]\ensuremath{\rightarrow}{[A,2]}, [B,2]\ensuremath{\rightarrow}{[B,2]}^{3^q}\}$
	$\cup \{ a_j\ensuremath{\rightarrow}a_j \;\vert\;1\leq j\leq {\ell}\},$

where $t$ is the value and $q$ is the length of $z_{a_k}$. By these tables we can introduce letters $a_k$ into the sentential form and at the same time we can modify the sentential form in such a way that it represents the act of concatenating the pair $(\lambda, z_{a_k})$ to a pair $(u_{s_1}\cdots u_{s_r}, v_{s_1}\cdots v_{s_r}z_{x_1}\cdots z_{x_v})$, $1\leq r$, $0\leq v.$ Hence by the end of the second phase we have a sentential form representing $(u_{s_1}\cdots u_{s_r}, v_{s_1}\cdots v_{s_r}z_{x_1}\cdots z_{x_n})$ and the corresponding word $x_1\cdots x_n$.

From now on, the derivation is done by table $T_3$. This consists of the following rules:

$$T_3=\{[A,2]\ensuremath{\rightarrow}[A,3], [B,2]\ensuremath{\right... ...th{\rightarrow}a_j\ensuremath{{{\overline{a}}}}_j\;\vert\;1\leq j\leq {\ell}\}.$$

By this set of rules we check whether or not the obtained sentential form $w$ satisfies ${\vert w\vert}_{[A,3]}\geq {\vert w\vert}_{[\ensuremath{{{\overline{B}}}},3]}$. If there are at least as many $[A,3]$'s as $[\ensuremath{{{\overline{B}}}},3]$'s in $w$, then no complementary transition takes place and the derivation can go on. Otherwise in the next derivation step a blocking situation occurs, the system will introduce symbols $K$. (We mentioned at the beginning of the proof, that all the letters not mentioned here, including $[\ensuremath{{{\overline{A}}}},3]$ and $[B,3]$, are rewritten to $K$.)

The next table is $T_4$, with the rules

$$T_4=\{[A,3]\ensuremath{\rightarrow}[\ensuremath{{{\overline{A}}}}... ...emath{\rightarrow}\ensuremath{{{\overline{a_j}}}}\;\vert\;1\leq j\leq {\ell}\}.$$

These rules are for checking whether or not the obtained sentential form $w$ satisfies ${\vert w\vert}_{[\ensuremath{{{\overline{A}}}},4]}\leq {\vert w\vert}_{[B,4]}$. We do it in the same way as we did in the previous case: if the sentential form goes through this checking as well, that is, if no complementary transition takes place, then the number of $A$'s and $B$'s are equal in $w$. Otherwise the system blocks the derivation in the next step.

Then the application of table $T_5$ follows, with rules

$$T_5=\{[\ensuremath{{{\overline{A}}}},4]\ensuremath{\rightarrow}\l... ...\overline{a_j}}}}\ensuremath{\rightarrow}\lambda \;\vert\;1\leq j\leq {\ell}\}.$$

These rules finish the derivation by deleting all symbols not in $\Delta$, therefore the derivation results in a word over alph$(L)$.

The construction of the standard Watson-Crick EDT0L system is based on the EPC representing the recursively enumerable language $L$ and it is guaranteed that only those terminal words $w=x_1\cdots x_n$ can be obtained by $\Sigma$ for which there exist some pairs $(u_{s_i},v_{s_i})$ in the EPC, such that $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}$. It is also clear that all these words can be derived, due to the working of the construct presented above. Moreover, from the construction we can also see that any terminal word that can be generated by the system is over $\Delta,$ letters from $\ensuremath{{{\overline{\Delta}}}}$ do not occur in a the generated words. Since these words are exactly the words of $L$, we have proved that $L(\Sigma)=L$. Moreover, we also can observe that the number of non-terminal letters is bounded by a constant, namely 28. height 5pt width 5pt depth 0pt

We note here that the only place where Watson-Crick complementarity is used is the third phase, where we check the equality of letters $A$ and $B$.