Standard Watson-Crick eco-grammar systems

In this part of the chapter we introduce standard Watson-Crick eco-grammar systems and we show that for any recursively enumerable language $L$ we can construct a standard Watson-Crick eco-grammar system generating it. Furthermore, in this standard Watson-Crick eco-grammar system there is only one agent and the set of the environment is deterministic.

Definition 6.7  
A standard Watson-Crick eco-grammar system is a construct $\Sigma=(V_E,P_E, R_1,$ $R_2, \ldots, R_n,\omega,\Delta )$ with the following properties: $V_E$ is a DNA-like alphabet, $P_E$ is a complete set of CF rules over $V_E$, $n\geq 1$, $R_i$ is a set of CF rules over $V_E$ (for $1\leq i \leq n$), which is the set of the $i$th agent, $\omega\in V^*$ is the axiom (which contains more purines than pyrimidines), and $\Delta$ is a subset of $V_E$.

The derivation goes in the same way as in an extended simple EG system, the only difference is that whenever a word with more pyrimidines than purines would be derived, a complementary transition takes place.

Definition 6.8  
Consider a standard Watson-Crick eco-grammar system $\Sigma=(V_E,P_E, R_1,R_2,$ $\ldots, R_n ,\omega,\Delta)$. We say that $x$ directly derives $y$ in $\Sigma$ (with $x,y\in {V_E}^*$, written as $x\ensuremath{{\stackrel{\text{W-eco}}{\Longrightarrow}}_{\Sigma}}y$), if $x=x_1A_1x_2\cdots A_{n-1}x_nA_nx_{n+1}$, $y={y_1}{z_1}{y_2}\cdots z_{n-1} {y_n}z_ny_{n+1}$, with $x_{\ell}\in V^*$, $A_j\in V$, $y_{\ell},z_j\in V^*$ for $1\leq {\ell}\leq n+1, \;1\leq j\leq n$, and there is a permutation of the agents, namely $R_{k_1}, \ldots, R_{k_n}$, such that there are rules $A_i\ensuremath{\rightarrow}{z_i}'$ in $R_{k_i}$ for $1\leq i \leq n$ and $x_1x_2\cdots x_{n+1}={y_1}'{y_2}'\cdots{y_{n+1}}'=\lambda$ or $x_1x_2\cdots x_{n+1}\ensuremath{{\stackrel{\text{0L}}{\Longrightarrow}}_{\ensuremath{{{\overline{\Sigma}}}}}}{y_1}'{y_2}'\cdots{y_{n+1}}'$ holds with the E0L system $\ensuremath{{{\overline{\Sigma}}}}=(V_E,P_E,\omega,\Delta)$ (considering it as a non-Watson-Crick system), and if ${\vert y'={y_1}'{z_1}'{y_2}'\cdots{z_n}'}$ ${{y_{n+1}}'\vert}_{V_{\text{PUR}}}\geq {\vert y'={y_1}'{z_1}'{y_2}'}$ ${\cdots {z_n}'{y_{n+1}}'\vert}_{V_{\text{PYR}}}$, then $y_{\ell}={y_{\ell}}'$ and ${z_j}={z_j}'$ for every $1\leq {\ell}\leq n+1$ and for every $1\leq j\leq n$, otherwise $y_{\ell}=h_w({y_{\ell}}')$ and ${z_j}=h_w({z_j}')$ for every $1\leq {\ell}\leq n+1$ and for every $1\leq j\leq n$.

In the above definition $h_w$ is the Watson-Crick morphism which assigns to each word its complementary word.

Informally speaking, in a derivation step first each agent chooses one position to apply a rule, then the remaining letters are rewritten by the environment. If after this rewriting the word contains more pyrimidines than purines, then all letters turn into their complementary letter and the derivation continues from this word, otherwise the derivation continues without a complementary transition.

We denote the transitive and reflexive closure of $\ensuremath{{\stackrel{\text{W-eco}}{\Longrightarrow}}_{}}{\Sigma}$ by ${\ensuremath{{\stackrel{\text{W-eco}}{\Longrightarrow}}_{}}{\Sigma}}^{*}$.

The generated language consists of the 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-eco}}{\Longrightarrow}}_{}}{\Sigma}}^{*}v \}.$$

Now we give a standard Watson-Crick eco-grammar system, as an example, and show that although the system contains only one agent and its rules are simple, it is able to generate a non-ET0L language (the same as in Example 5.10 and 6.1).

Example 6.9  
Let $\Sigma=(\;V,P, R_1,\omega, \Delta\;)$ be the following standard Watson-Crick eco-grammar system:

• $V=\{a,b, K, \ensuremath{{{\overline{a}}}}, \ensuremath{{{\overline{b}}}},\ensuremath{{{\overline{K}}}}\}\;\cup[W,0]\cup[W,1]$, where
  $W=\left\{a,\ensuremath{{{\overline{a}}}}, c, \ensuremath{{{\overline{c}}}}, b,... ..., \ensuremath{{{\overline{S_1}}}}, S_2, \ensuremath{{{\overline{S_2}}}}\right\}$,
• $P=\left\{\; [a,0]\ensuremath{\rightarrow}[a,0], [\ensuremath{{{\overline{c}}}}... ...rline{D}}}},0]\ensuremath{\rightarrow}[\ensuremath{{{\overline{D}}}},0],\right.$
  $\left. [N,0]\ensuremath{\rightarrow}[N,0], [\ensuremath{{{\overline{M}}}},0]\ensuremath{\rightarrow}[\ensuremath{{{\overline{M}}}},0]\right\}\;\cup$
  
  
  $\left\{[\ensuremath{{{\overline{a}}}},0]\ensuremath{\rightarrow}[a,1], [{c},0]... ...[B,1], [{D},0]\ensuremath{\rightarrow}[\ensuremath{{{\overline{D}}}},1],\right.$
  $\left.[\ensuremath{{{\overline{N}}}},0]\ensuremath{\rightarrow}[N,1], [{M},0]\ensuremath{\rightarrow}[\ensuremath{{{\overline{M}}}},1]\right\}\;\cup$
  
  
  $\left\{[a,1]\ensuremath{\rightarrow}[a,1], [\ensuremath{{{\overline{c}}}},1]\e... ...ine{D}}}},1]\ensuremath{\rightarrow}[\ensuremath{{{\overline{D}}}},1], \right.$
  $\left. [N,1]\ensuremath{\rightarrow}[N,1], [\ensuremath{{{\overline{M}}}},1]\e... ...[L,1]\ensuremath{\rightarrow}[L,1], [b,1]\ensuremath{\rightarrow}[b,1], \right.$
  $\left. [\ensuremath{{{\overline{d}}}},1]\ensuremath{\rightarrow}[\ensuremath{{... ...{\rightarrow}[S_1,1]\;\vert\;[\ensuremath{{{\overline{S_2}}}},1] \;\right\}\cup$
  
  
  $\left\{[\ensuremath{{{\overline{a}}}},1]\ensuremath{\rightarrow}a, [{c},1]\ens... ...bda, [\ensuremath{{{\overline{B}}}},1]\ensuremath{\rightarrow}\lambda, \right.$
  $\left.[{D},1]\ensuremath{\rightarrow}\lambda, [\ensuremath{{{\overline{L}}}},... ..., [\ensuremath{{{\overline{N}}}},1]\ensuremath{\rightarrow}\lambda \right\}\cup$
  
  
  $\left\{[X,0]\ensuremath{\rightarrow}K, [X,1]\ensuremath{\rightarrow}K\;\vert\;\right.$ for the other $\left.X\in W \right\}\cup$
  $\{a\ensuremath{\rightarrow}K, {b}\ensuremath{\rightarrow}K, K\ensuremath{\righ... ...ath{\rightarrow}K, \ensuremath{{{\overline{K}}}}\ensuremath{\rightarrow}K\;\}$
• $\omega=[S_1,0]$,
• $\Delta=\{\;a,b\;\}$, and
• $R_1=\left\{\; [S_1,0]\ensuremath{\rightarrow}[a,0][\ensuremath{{{\overline{c}}... ...verline{D}}}},0][N,0] [\ensuremath{{{\overline{M}}}},0][S_1,0]\;\vert\; \right.$
  $\left.[a,0][\ensuremath{{{\overline{c}}}},0][B,0][\ensuremath{{{\overline{D}}}... ...,0]\ensuremath{\rightarrow}[S_1,1], [N,1]\ensuremath{\rightarrow}[L,1], \right.$
  $\left. [S_2,1]\ensuremath{\rightarrow}\lambda \;\right\}$.

We show that the generated language of this system is

$$L(\Sigma)=\{\;{(ab^n)}^m\;\vert \; 1\leq n\leq m\;\},$$

which is not an ET0L language (see [Rozenberg and SalomaaRozenberg and Salomaa1980]).

The working of the system is divided into three phases. In the first phase the agent uses several times the rule $[S_1,0]\ensuremath{\rightarrow}[a,0][\ensuremath{{{\overline{c}}}},0][B,0][\ensuremath{{{\overline{D}}}},0][N,0]$ $[\ensuremath{{{\overline{M}}}},0][S_1,0]$ and the environment does not alter anything. In this way the sentential form becomes a word in the form $[{(a\ensuremath{{{\overline{c}}}}B\ensuremath{{{\overline{D}}}}N\ensuremath{{{\overline{M}}}})}^{m-1}S_1,0]$, with $m\geq 1$. When finally the agent uses the rule $[S_1,0]\ensuremath{\rightarrow}[a,0][\ensuremath{{{\overline{c}}}},0][B,0][\ensuremath{{{\overline{D}}}},0][N,0]$ $[\ensuremath{{{\overline{M}}}},0][\ensuremath{{{\overline{S_2}}}},0]$, a word with more pyrimidines than purines would be generated, thus a complementary transition takes place and the word $[{(\ensuremath{{{\overline{a}}}}{c}\ensuremath{{{\overline{B}}}}{D}\ensuremath{{{\overline{N}}}}{M})}^{m}S_2,0]$ results. Then the agent rewrites $[S_2,0]$ to $[S_1,1]$ and the environment changes the indices from 0 to 1 and rewrites the letters into their complementary symbols. Hence the sentential form becomes $[{({a}\ensuremath{{{\overline{c}}}}{B}\ensuremath{{{\overline{D}}}}{N}\ensuremath{{{\overline{M}}}})}^{m}S_1,1]$.

At this point the only rule which is available for the agent is $[N,1]\ensuremath{\rightarrow}[L,1]$. While the agent rewrites the letters $N$ to letters $L$, the environment writes words $b\ensuremath{{{\overline{d}}}}$ before the letters $B$. This can happen at most $m$ times, because after this the agent cannot work, the derivation is blocked. At the $n$th iteration of this step, at most in the $m$th step, the environment must use the rule $[S_1,1]\ensuremath{\rightarrow}[\ensuremath{{{\overline{S_2}}}},1]$, which results in a complementary transition and the sentential form becomes a word in the form of $[{(\ensuremath{{{\overline{a}}}}{c}{(\ensuremath{{{\overline{b}}}}{d})}^n\ensuremath{{{\overline{B}}}}{D}\ensuremath{{{\overline{N}}}}{M})}^{m-n}$ ${(\ensuremath{{{\overline{a}}}}{c}{(\ensuremath{{{\overline{b}}}}d)}^n\ensuremath{{{\overline{B}}}}{D}\ensuremath{{{\overline{L}}}}{M})}^{n} S_2,1]$.

From this point the derivation is finished in one step: the agent deletes the symbol $S_2$, the environment deletes all letters, except the letters $\ensuremath{{{\overline{a}}}}$ and $\ensuremath{{{\overline{b}}}}$, which are rewritten into terminal form.

In this way all the words in the form of ${(ab^n)}^m$, with $1\leq n\leq m$ can be generated and it is clear from the construction that the working explained above is the only possibility to generate a terminal word.

This example shows how a standard Watson-Crick eco-grammar system works and illustrates the power of these systems as well. Let us note that in this example the environment is not deterministic, there are two rules for the symbol $[S_1,1]$. The construction of the following theorem prove that we could avoid this non-determinism: all recursively enumerable language can be generated by standard Watson-Crick eco-grammar systems with only one agent, and with a deterministic environment.

Theorem 6.10  
Let $L$ be a recursively enumerable language. Then there exists a standard Watson-Crick eco-grammar system ${\Sigma}_1=(V_1, P_1, R_1, {\omega}_1, {\Delta}_1)$, such that $L=L({\Sigma}_1)$, and $P_1$ is deterministic.

PROOF.
For $L$, we construct ${{\Sigma}_1}$ by modifying the construction of the standard Watson-Crick E0L system $\Sigma$ presented in the proof of Theorem 6.5. The alphabet, the terminal alphabet and the axiom of ${\Sigma}_1$ are the same as the ones in $\Sigma$. Moreover, $P_1$, the set of the environment in ${\Sigma}_1$, contains all the rules of $P$ except those which rewrites an $S$ letter being in any form, therefore $P_1$ is a deterministic set. Instead of these rules, to make the set $P_1$ complete, we put the rules $[X, i]\ensuremath{\rightarrow}K$ and $[X, k, 1]\ensuremath{\rightarrow}K$ into $P_1$, where $X\in \{S_{in}, S_{out}, S_{out}^0, \ensuremath{{{\overline{S_{in}}}}}, \ensuremath{{{\overline{S_{out}}}}}, \ensuremath{{{\overline{S_{out}^0}}}}\}$, $0\leq i\leq m+{\ell}+4$, and $1\leq k\leq m+{\ell}+2$.

The set of the agent, $R_1$, contains all the $S$ rewriting rules of $P$ where $S$ is in the form of $[X,i]$ or $[X,k,1]$ with $X\in \{S_{in}, S_{out}, S_{out}^0, \ensuremath{{{\overline{S_{in}}}}}, \ensuremath{{{\overline{S_{out}}}}}, \ensuremath{{{\overline{S_{out}^0}}}}\}$, $0\leq i\leq m+{\ell}+4$, and $1\leq k\leq m+{\ell}+2$. Moreover, in order to guarantee that the agent could work in the last two steps (if the sentential form is not empty), we also put the following rules into $R_1$: $[A, m+{\ell}+3]\ensuremath{\rightarrow}[\ensuremath{{{\overline{A}}}}, m+{\ell}+3]$, $[\ensuremath{{{\overline{A}}}},m+{\ell}+4]\ensuremath{\rightarrow}\lambda$.

It is clear from the construction of ${\Sigma}_1$ that it works in the same way as $\Sigma$ in Theorem 6.5; the only difference is that the choices are made by the agent, not by the E0L set. Thus $L({\Sigma}_1)= L$, which completes the proof.height 5pt width 5pt depth 0pt