Weak extended simple eco-grammar systems

In this section another variant of extended simple eco-grammar systems is studied: the weak extended simple eco-grammar system. This variant has the same components as an extended simple eco-grammar system but it works in a different way.

Definition 5.13  
A weak extended simple eco-grammar system (a wEEG system, for short) is a construct , where all the components are the same as in Definition 2.4.


In a weak extended simple eco-grammar system $x$ directly derives $y$ $(with\;\;x,y\in {V_E}^*$, written as $x \ensuremath{{\stackrel{\text{w-eco}\;} {\Longrightarrow}}_{\Sigma}} y$), if

• $x=x_1Z_1x_2Z_2\cdots x_kZ_kx_{k+1}$, with $Z_i\in V_E$, $x_j\in {V_E}^*$, $0\leq k\leq n$, $1\leq i\leq k$, and $1\leq j\leq k+1$,
• $y=y_1w_1y_2w_2\cdots y_kw_ky_{k+1}$, with $y_i, w_j\in {V_E}^*$, $0\leq k\leq n$, $1\leq i\leq k$, and $1\leq j\leq k+1$,
• there exists a permutation of some agents, namely $R_{j_1},R_{j_2},\ldots,R_{j_k}$, such that $Z_i\ensuremath{\rightarrow}w_i\in R_{j_i}$ for $1\leq i\leq k$,
• dom$(R_t)\cap$   alph$(x_1x_2\cdots x_{k+1})=\emptyset$, for $1\leq t\leq n, t\not = {j_i}$, $1\leq i\leq k$ and
• $x_1x_2\cdots x_{k+1}=y_1y_2\cdots y_{k+1}=\lambda$ or $x_1x_2\cdots x_{k+1}\ensuremath{{\stackrel{\text{0L}}{\Longrightarrow}}_{E}}y_1y_2\cdots y_{k+1}$, where $E=( V_E, P_E, \omega )$ is the 0L system of the environment.

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

Informally speaking, in a weak extended simple eco-grammar system we choose some agents to perform a common action in the following way: the chosen agents can perform an action together and there is no symbol among the remaining letters where any of the other agents could act. The chosen agents perform their actions, the remaining letters are rewritten by the environment. In that particular case when there is only one agent in the system, this definition implies that the agent has to work if it is able to but if no letter can be rewritten by the agent, then it is the environment itself that continues the derivation.

Definition 5.14  
For a weak extended simple eco-grammar system
the generated language is the following:

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

In the following we show that wEEG systems can generate all recursively enumerable languages. The result is based on the following lemma.

Lemma 5.15  
Let $L$ be a language in ${\mathcal{RC}}_{ac}^{\lambda}$. Then there exists a weak extended simple eco-grammar system $\Sigma$ with one agent, such that $L(\Sigma)=L$.

PROOF.
Let $L$ be a language in ${\mathcal{RC}}_{ac}^{\lambda}$. As in Lemma 5.11, we can suppose that $L$ can be generated by a a random-context grammar with complete checking $G=(N,T,S,P)$, where the rules in $P$ have the form $(C\ensuremath{\rightarrow}\alpha, Q, R)$, with $C\in N$, $\alpha\in {(N\cup T)}^*$, card$(Q)\leq 1$, and card$(R)\leq 1$. By the note at the end of the proof of Lemma 5.6, we can assume that there are no rules with $Q=R$, $R=\{C\}$ or $Q=\{C\}$. We will give a weak extended simple eco-grammar system $\Sigma=(V_E, P_E, R_1, \Delta, \omega)$, such that $L(G)=L(\Sigma)$.

We present the definition of this system $\Sigma$ and explain its functioning. Similar to Lemma 5.11, the notation $V$ stands for $N\cup T$, $r$ denotes the number of rules in $P$, the rules in $P$ are enumerated as $p_i=(C_i\ensuremath{\rightarrow}{\alpha}_i,Q_i,R_i)$.

Let

• $V_E= V\cup \;\{[X,i,j]\;\vert\;X\in V, 1\leq i\leq r, 1\leq j\leq 5\}$
  $\cup \;\{[Z,i,j],[\widehat{Z},i,k]\;\vert\;1\leq i\leq r, 1\leq j\leq 5, 1\leq k\leq 4\}$
  $\cup\;\{[{\widehat{C}}_i,i,k]\;\vert\; 1\leq i\leq r, 1\leq k\leq 4\}$
  $\cup\;\{[U,i,{\ell}]\;\vert\;1\leq i\leq r, Q_i=\emptyset, 1\leq {\ell}\leq 2\}$
  $\cup\;\{K\}\;$
  $\cup \{[K,i,3]\;\vert\;1\leq i\leq r\}$ where $U,K,Z\not \in V$,
• $P_E= \{[X,i-1,5]\ensuremath{\rightarrow}[X,i,1]\;\vert\;2\leq i\leq r, X\in V\cup \{Z\}\}$
  $\cup \;\{[X,r,5]\ensuremath{\rightarrow}[X,1,1]\;\vert\;X\in V\cup \{Z\}\}$
  
  $\cup \;\{[X,i,1]\ensuremath{\rightarrow}[X,i,2]\;\vert\;1\leq i\leq r, X\in V\cup \{Z, \widehat{Z}\}\}$
  $\cup \;\{[{\widehat{C}}_i,i,1]\ensuremath{\rightarrow}[{\widehat{C}}_i,i,2]\;\vert\; 1\leq i\leq r\}$
  $\cup \;\{[U,i,1]\ensuremath{\rightarrow}[U,i,2]\;\vert\;1\leq i\leq r, Q_i=\emptyset\}$
  
  $\cup \;\{[X,i,2]\ensuremath{\rightarrow}[X,i,3]\;\vert\;1\leq i\leq r, X\in V\cup \{Z, \widehat{Z}\}\}$
  $\cup \;\{[{\widehat{C}}_i,i,2]\ensuremath{\rightarrow}[{\widehat{C}}_i,i,3]\;\vert\; 1\leq i\leq r\}$
  $\cup \;\{[U,i,2]\ensuremath{\rightarrow}K\;\vert\;1\leq i\leq r, Q_i=\emptyset\}$
  
  $\cup \;\{[X,i,3]\ensuremath{\rightarrow}[X,i,4]\;\vert\;1\leq i\leq r, X\in V\cup \{Z, \widehat{Z}\}\}$
  $\cup \;\{[{\widehat{C}}_i,i,3]\ensuremath{\rightarrow}[{\widehat{C}}_i,i,4]\;\vert\; 1\leq i\leq r\}$
  $\cup\;\{[K,i,3]\ensuremath{\rightarrow}K\;\vert\;1\leq i\leq r\}$
  
  $\cup \;\{[X,i,4]\ensuremath{\rightarrow}[X,i,5]\;\vert\;1\leq i\leq r, X\in V\cup \{Z\}\}$
  $\cup\;\{[\widehat{Z},i,4]\ensuremath{\rightarrow}[Z,i,5]\;\vert\;1\leq i\leq r\}$
  $\cup \;\{[{\widehat{C}}_i,i,4]\ensuremath{\rightarrow}[{C}_i,i,5]\;\vert\; 1\leq i\leq r\}$
  
  $\cup \;\{[X,i,5]\ensuremath{\rightarrow}X\;\vert\;1\leq i\leq r, X\in V\cup \{Z\}\}$
  $\cup\;\{X\ensuremath{\rightarrow}K\;\vert\; X\in V\cup \{K\}\}$,
• $R_1=\{[Z,i-1,5]\ensuremath{\rightarrow}[\widehat{Z},i,1]\;\vert\;2\leq i\leq r\}$
  $\cup\;\{[Z,r,5]\ensuremath{\rightarrow}[\widehat{Z},1,1]\}$
  $\cup \;\{[C_i,i-1,5]\ensuremath{\rightarrow}[{\widehat{C}}_i,i,1]\;\vert\;2\leq i\leq r, Q_i\not = \emptyset\}$
  $\cup \;\{[C_1,r,5]\ensuremath{\rightarrow}[{\widehat{C}}_1,1,1]\;\vert\;Q_1\not=\emptyset\}$
  $\cup \;\{[C_i,i-1,5]\ensuremath{\rightarrow}[{\widehat{C}}_i,i,1][U,i,1]\;\vert\;2\leq i\leq r, Q_i = \emptyset\}$
  $\cup \;\{[C_1,r,5]\ensuremath{\rightarrow}[{\widehat{C}}_1,1,1][U,1,1]\;\vert\;Q_1=\emptyset\}$
  
  $\cup\;\{[\widehat{Z},i,1]\ensuremath{\rightarrow}[\widehat{Z},i,2]\;\vert\;1\leq i\leq r\}$
  $\cup \;\{[B,i,1]\ensuremath{\rightarrow}K\;\vert\; 1\leq i\leq r, \{B\}=R_i\not=\emptyset\}$
  
  $\cup \;\{[A,i,2]\ensuremath{\rightarrow}[A,i,3][K,i,3]\;\vert\;1\leq i\leq r, \{A\}=Q_i\not =\emptyset\}$
  $\cup \;\{[U,i,2]\ensuremath{\rightarrow}[K,i,3]\;\vert\;1\leq i\leq r, Q_i=\emptyset\}$
  $\cup \;\{[\widehat{Z},i,2]\ensuremath{\rightarrow}[\widehat{Z},i,3]\;\vert\;1\leq i\leq r\}$
  
  $\cup \;\{[K,i,3]\ensuremath{\rightarrow}\lambda\}$
  $\cup\;\{[{\widehat{C}}_i,i,3]\ensuremath{\rightarrow}K\;\vert\;1\leq i\leq r, \}$
  
  $\cup \;\{[{\widehat{C}}_i,i,4]\ensuremath{\rightarrow}[{\alpha}_i,i,5]\;\vert\;1\leq i\leq r, {\alpha}_i\not =\lambda\}$
  $\cup \;\{[{\widehat{C}}_i,i,4]\ensuremath{\rightarrow}\lambda\;\vert\;1\leq i\leq r, {\alpha}_i=\lambda\}$
  
  $\cup\;\{[Z,i,5]\ensuremath{\rightarrow}\lambda \;\vert\;1\leq i\leq r\}$,
• $\Delta= T$, and
• $\omega=[S,r,5][Z,r,5]$.

The main point of the simulation is that we simulate the application of the rules in their order from $1$ to $r$, each time either simulating the rule or skipping it. After having simulated or skipped the $r$th rule we continue with the first one.

We do the simulation of a rule by introducing five different alphabets for each rule of $G$: for the $i$th rule we introduce the alphabets $[V,i,j]$ for $1\leq j\leq 5$. We start the simulation or the skipping of the $i$th rule with a word over the alphabet $[V,i-1,5]$, then during the simulation we go through the alphabets $[V,i,j]$ for $1\leq j\leq 4$, and finish with a word over the alphabet $[V,i,5]$. Consequently we can finish the whole derivation or we can continue with the next rule.

There are more additional alphabets for coordinating the simulation: the letters $[Z,i,j]$ and $[\widehat{Z},i,k]$ for $1\leq i\leq r$, $1\leq j\leq 5$, and $1\leq k\leq 4$ make it possible to skip the $i$th rule of $G$; the symbols $[{\widehat{C}}_i,i,k]$ let the agent simulate the $i$th rule of $G$; the symbols $[U,i,{\ell}]$ are introduced only if $Q_i$, the permitting set is empty and make it possible to deal with this case; the symbols $[K,i,3]$ ensure that the derivation is blocked if the agent simulates the $i$th rule of $G$ while the non-empty permitting condition is missing.

In the following, we first show how the application of a rule of $G$ can be simulated and we also show how the application can be skipped. Then we show why the construction of the above wEEG system guarantees that only those derivations result in a terminal word which follow a derivation of the random-context grammar $G$.

Let us suppose that we want to simulate the application of the first rule of $G$: $(C_1\ensuremath{\rightarrow}{\alpha}_1, Q_1,R_1)$ (the case of the other rules is similar) and let us first suppose that $Q_1\not=\emptyset$. Before the simulation the sentential form in $\Sigma$ is over $\{[W,r,5]\;\vert\; W\in V\cup\{Z\}\}$.

In the first step the agent ``decides'' whether the current rule (in this case the first rule of $G$) will be simulated or will be skipped. Let us suppose that the rule is to be simulated. In this case the agent uses the rule $[C_1,r,5]\ensuremath{\rightarrow}[{\widehat{C}}_1,1,1]$. The other letters are rewritten by the environment, using the rules $\{[X,r,5]\ensuremath{\rightarrow}[X,1,1]\;\vert\;X\in V\cup \{Z\}\}$.

In the next step the agent checks whether or not the forbidding context is present in the sentential form. This is done in the following way: the agent introduces a $K$ if $[B,1,1]$ is present (where $\{B\}=R_1$ is the forbidding context), while otherwise the agent does not work because $[\widehat{Z},1,1]$ is not present in the sentential form. The environment increases the second index of the symbols from 1 to 2 in this step.

In the third step the agent uses the rule $[A,1,2]\ensuremath{\rightarrow}[A,1,3][K,1,3]$ for $\{A\}=Q_1$; the environment increases the second indexes from 2 to 3 in the other symbols.

In the fourth step the agent deletes $[K,1,3]$ while the environment increases the second indexes from 3 to 4. In the fifth and final step the agent applies the rule $[{\widehat{C}}_1,1,4]\ensuremath{\rightarrow}[{\alpha}_1,1,5]$ or the rule $[{\widehat{C}}_1,1,4]\ensuremath{\rightarrow}\lambda$, which correspond to the first rule of $G$; the environment increases the second indexes. Therefore we obtain a word over $\{[W,1,5]\;\vert\;W\in V\cup \{Z\}\}$.

If $Q_1=\emptyset$, that is, when the permitting condition is empty, then the simulation is different. While the environment does the same as in the previous case, the agent applies different rules. The rule the agent uses in the first step is $[C_1,r,5]\ensuremath{\rightarrow}[{\widehat{C}}_1,1,1][U,1,1]$ and thus $[U,1,1]$ is introduced. In the third step this symbol is used to introduce $[K,1,3]$ and from that point the simulation continues in the same way as described above, that is, when $Q_1\not=\emptyset$.

Now we show how we can do the skipping of the first rule (the case of the other rules is the same). Let us suppose again that we have a word over the alphabet $\{[W,r,5]\;\vert\; W\in V\cup\{Z\}\}$.

The environment works in the same way as it did in the previous case, the difference is in the behaviour of the agent. In the first step the agent chooses the rule $[Z,r,5]\ensuremath{\rightarrow}[\widehat{Z},1,1]$, in the next step the rule $[\widehat{Z},1,1]\ensuremath{\rightarrow}[\widehat{Z},1,2]$, and in the third step the rule $[\widehat{Z},1,2]\ensuremath{\rightarrow}[\widehat{Z},1,3]$. In the fourth and in the fifth step the agent no longer has any rule to apply, hence it does not perform any action. By the end of these five steps we have the same word as we had before, apart from the first indexes in the symbols: we have the same word over the alphabet $\{[W,1,5]\;\vert\;W\in V\cup \{Z\}\}$.

At this point the simulation or the skipping of the second rule can start and can be carried out in the previous manner. We can continue this process until the last rule, the $r$th one, when we can restart the whole procedure with the first rule again.

In order to finish the derivation, after having finished the simulation of a rule of $G$ the agent chooses the rule in the form of $[Z,i,5]\ensuremath{\rightarrow}\lambda$ while the environment rewrites the remaining letters according to its rules $[X,i,5]\ensuremath{\rightarrow}X$. Thus we have seen that $L(G)\subseteq L(\Sigma).$

In the following we show that the eco-grammar system must follow one of the sequences presented above, or otherwise the derivation would never terminate.

In the first step, when the sentential form is over $[W,i-1,5]$, the agent can work because either the left-hand side of the current rule of $G$ is present (and thus the agent can rewrite $[C_i,i-1,5]$) or the symbol $[Z,i-1,5]$ can be rewritten. (At the end of the proof we explain why we can suppose that $Z$ has not yet disappeared from the sentential form.)

Therefore, in this first step the agent marks a position where it can perform the application of the current rule or it can mark $Z$. If it marks a position for the current rule, then in the next steps it must check the appearance of the forbidding and the permitting context. The derivation can result in a word not containing letters $K$ only if the check is successful. This is done in the following way: the derivation is blocked by the rule $[B,i,1]\ensuremath{\rightarrow}K$ if the forbidding context is present, or by the rule $[{\widehat{C}}_i,i,3]\ensuremath{\rightarrow}K$ if the non-empty permitting condition is missing. In the last step the agent must apply the rule corresponding to the rule of $G$.

Thus we have seen that if the agent decides to mark a position for applying the current rule, then it must check whether or not the rule is applicable, and, if the checking is successful, then finally it must simulate it. If the agent chooses the other possibility and marks $Z$, then in the next two steps he must increase the second index of $[\widehat{Z},i,j]$ from 1 to 2 and from 2 to 3. In the next two steps the agent cannot work. Hence if the agent chooses to mark $[Z,i,5]$, then the work of the whole system follows the strategy of skipping the current rule, or otherwise the derivation would be blocked.

As far as the end of the derivation is concerned, the environment has to apply the rules in the form of $[X,i,5]\ensuremath{\rightarrow}X$ for all the letters in the same derivation step, or otherwise the derivation is blocked in the next step. It can happen that the agent deletes $Z$ before the end of the derivation but this fact does not allow any new word to be generated, so we can safely assume that the deletion of $Z$ happens in the same derivation step as the rewritings $[X,i,5]\ensuremath{\rightarrow}X$. We have seen the other direction of the inclusion, $L(\Sigma)\subseteq L(G)$, which completes the proof of the lemma.height 5pt width 5pt depth 0pt

Because ${\mathcal{RC}}_{ac}^{\lambda}=\mathcal{RE}$, we obtain the following theorem:

Theorem 5.16  
Let $L$ be a recursively enumerable language. Then there exists a weak extended simple eco-grammar system $\Sigma$ with one agent, such that $L(\Sigma)=L$.