Extended tabled simple eco-grammar systems

In this section extended tabled simple eco-grammar systems are investigated. In such a system the environment can be represented by more than one 0L system.

Definition 5.7  
An extended tabled simple eco-grammar system $($an ETEG system, for short$)$ is a construct $\Sigma=(\:V_E,T_E,R_1,\ldots,$ , where

• $(V_E,T_E,\omega, \Delta)$ is an ET0L system,
• $n\geq 1$, and
• $R_i$ is a non-empty set of CF rules over $V_E$ for $1\leq i \leq n$.

Here $V_E$, $n$, $R_i$ (for $1\leq i \leq n$), $\omega$ and $\Delta$ have the same meaning as in Definition 2.4, that is, these are the alphabet of the system, the number of the agents, the production sets representing the agents, the axiom, and the terminal alphabet. $T_E=\{T_i\;\vert\;1\leq i\leq k\;\}$ is the set of tables of the environment, where each $T_i$ is a complete set of CF rules over $V_E$.

In an extended tabled simple eco-grammar system the environment in each derivation step can choose a table to perform a parallel rewriting.

Definition 5.8  
Consider an extended tabled simple eco-grammar system $\Sigma=(\:V_E,T_E,R_1,\ldots,$ , where $T_E=\{T_i\;\vert\;1\leq i\leq k\;\}$. We say that $x$ directly derives $y$ in $\Sigma$ $($with $x,y\in {V_E}^*$, written as $x \ensuremath{{\stackrel{\text{t-eco}\;} {\Longrightarrow}}_{\Sigma}} y)$ if $x \ensuremath{{\stackrel{\text{eco}\;\;} {\Longrightarrow}}_{{\Sigma}_i}} y$ holds with the extended simple eco-grammar system ${\Sigma}_i=(V_E,T_i,R_1,\ldots,R_n,\omega,\Delta)$ for some $1\leq i\leq k$.

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

Definition 5.9  
The generated language of an extended tabled simple eco-grammar system $\Sigma=(\:V_E,T_E,R_1,\ldots,$ is the following:

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

Now we present an example to illustrate the power of ETEG systems.

Example 5.10  
Let $\Sigma=(\;V_E,T_E,R_1,\omega,\Delta\;)$ be the following ETEG system:

• $V_E=\{\;S,B,N,K,S',a,b\;\}$,
• $T_E=\{\;T_1,T_2,T_3,T_4\;\}$, where
  $T_1=\{\;S\ensuremath{\rightarrow}K, N\ensuremath{\rightarrow}N, a\ensuremath{... ...th{\rightarrow}K, S'\ensuremath{\rightarrow}S', B\ensuremath{\rightarrow}B \;\}$,
  $T_2=\{\;S\ensuremath{\rightarrow}\lambda, N\ensuremath{\rightarrow}N, a\ensur... ...ath{\rightarrow}K, S'\ensuremath{\rightarrow}K, B\ensuremath{\rightarrow}B \;\}$,
  $T_3=\{\;S\ensuremath{\rightarrow}K, N\ensuremath{\rightarrow}N, a\ensuremath{\... ...th{\rightarrow}K, S'\ensuremath{\rightarrow}K, B\ensuremath{\rightarrow}bB\;\}$,
  $T_4=\{\;S\ensuremath{\rightarrow}K, N\ensuremath{\rightarrow}N, a\ensuremath{\... ...ath{\rightarrow}K, S'\ensuremath{\rightarrow}K, B\ensuremath{\rightarrow}b\;\}$,
• $R_1=\{\;S\ensuremath{\rightarrow}aBNS, N\ensuremath{\rightarrow}\lambda, S'\ensuremath{\rightarrow}\lambda\;\}$,
• $\omega=SS'$, and
• $\Delta=\{\;a,b\;\}$.

We show that the generated language of this system is

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

First we note that $S$ can be deleted only by the environment and $S'$ can be deleted only by the agent, and that these two events must happen in the same derivation step. If the environment deletes $S$, that is, it uses table $T_2$, and the agent does not apply the rule $S'\ensuremath{\rightarrow} \lambda$, then the environment rewrites $S'$ to $K$, which blocks the derivation since this $K$ will never disappear from the sentential form. If the agent deletes $S'$ in a derivation step and the environment does not delete $S$, that is, does not use table $T_2$, then it introduces symbol $K$ again.

Before this step, when $S$ and $S'$ disappear from the sentential form, in every step the agent has to use the rule $S\ensuremath{\rightarrow}aBNS$, or otherwise the environment introduces a $K$, and the environment has to use the first table $T_1$, or otherwise $S'$ would be rewritten to $K$. Thus either the derivation is $SS' \ensuremath{{\stackrel{\text{t-eco}}{\Longrightarrow}}_{}}\lambda$, or the first few steps are $SS' {\ensuremath{{\stackrel{\text{t-eco}\;} {\Longrightarrow}}_{}}}^{*} {(aBN)}^{m}SS' \ensuremath{{\stackrel{\text{t-eco}}{\Longrightarrow}}_{}} {(aBN)}^{m}$. After these steps the only possibility for the agent is to use rule the $N\ensuremath{\rightarrow}\lambda$. During these steps the environment can use any of its tables, therefore it can introduce letters $b$ before all the $B$'s or it can rewrite either all letters $B$ to $B$ or all letters $B$ to $b$. Because there are only $m$ symbols $N$ in the sentential form, the derivation lasts exactly $m$ more steps. Hence at the end of the derivation, when there are no more $N$ symbols left, there are at least one but at most $m$ symbols $b$ after each $a$.

The above explication shows that all non-empty generated words are in the form ${(ab^n)}^m$, $1\leq n\leq m$. It follows from the construction that all words of this form and the empty word, $\lambda$, too, are in the generated language, which is thus indeed:

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

This example shows that even a very simple extended tabled simple eco-grammar system with only one agent is able to produce a quite complicated language, namely a language which is not an ET0L one (see [Rozenberg and SalomaaRozenberg and Salomaa1980]).


We show that these systems can generate all recursively enumerable languages. This result is a direct consequence of the following lemma.

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

PROOF.
Let $L$ be a language in ${\mathcal{RC}}_{ac}^{\lambda}$. By Lemma 5.5 we can suppose that $L=L(G)$ with a random-context grammar with complete checking $G=(N,T,S,P)$. By Lemma 5.6 we can suppose that 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$. Moreover, 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 denote by $r$ the number of rules in $P$ and by $V$ the set $N\cup T$. The rules of $P$ are enumerated as $p_i=(C_i\ensuremath{\rightarrow}{\alpha}_i,Q_i,R_i)$. We will refer to the components of the $i$th rule as $C_i$, ${\alpha}_i$, $Q_i$, and $R_i$.

Now we will construct an extended tabled simple eco-grammar system
$\Sigma=(V_E,T_E,R_1,\omega,\Delta)$, such that $L(\Sigma)=L(G)=L.$ Let

$V_E=V$	$\cup \;\{[X,i]\;\vert\;X\in V, 1\leq i\leq r\}$
	$\cup\;\{[X',i]\;\vert\;X\in V, 1\leq i\leq r\}$
	$\cup\;\{K,U,Z,Z'\}$
	$\cup \;\{[U,i]\;\vert\;1\leq i\leq r, Q_i=\emptyset\}$
	$\cup\;\{[U',i]\;\vert\;1\leq i\leq r\}$
	$\cup\;\{[\widehat{U},i]\;\vert\;1\leq i\leq r, Q_i\not=\emptyset\},$
	where $K,U,Z, Z'\not\in V,$

$T_E=$

$\{T_{i}, {T'}_{i}, {T''}_{i}\;\vert\;1\leq i\leq r\}, \;$where

$T_{i}=$	$\{X\ensuremath{\rightarrow}[X,i]\;\vert\;X\in V\}$
	$\cup \;\{U\ensuremath{\rightarrow}[U,i]\;\vert\; Q_i=\emptyset\}$
	$\cup\;\{U\ensuremath{\rightarrow}[\widehat{U},i]\;\vert\;Q_i\not =\emptyset\},$
	for $1\leq i\leq r,$

${T'}_{i}=$	$\{[X,i]\ensuremath{\rightarrow}[X',i]\;\vert\;X\in V, \{X\}\not =R_i\}$
	$\cup \;\{[B,i]\ensuremath{\rightarrow}K\;\vert\;\{B\}=R_i\}$
	$\cup \;\{Z'\ensuremath{\rightarrow}Z'\}\;$
	$\cup\;\{[\widehat{U},i]\ensuremath{\rightarrow}[U',i]\;\vert\;Q_i\not = \emptyset\}$
	for $1\leq i\leq r,$

${T''}_{i}=$	$\{[X',i]\ensuremath{\rightarrow}X\;\vert\;X\in V\}$
	$\cup \;\{Z'\ensuremath{\rightarrow}Z, Z'\ensuremath{\rightarrow}\lambda, [U',i]\ensuremath{\rightarrow}U,[U',i]\ensuremath{\rightarrow}\lambda\}$
	for $1\leq i\leq r,$

$R_1=$	$\{Z\ensuremath{\rightarrow}Z'\}$
	$\cup \;\{[U,i]\ensuremath{\rightarrow}[U',i]\;\vert\;1\leq i\leq r, Q_i=\emptyset\}$
	$\cup \;\{[A,i]\ensuremath{\rightarrow}[{A'},i]\;\vert\;1\leq i\leq r, Q_i=\{A\}\}$
	$\cup \;\{[{C'}_i,i]\ensuremath{\rightarrow}{\alpha}_i\;\vert\;1\leq i\leq r\},$

$\omega=$

$SUZ,$ and

$\Delta=$

$T.$

Those symbols which are not mentioned above in the tables are rewritten into $K$; these rules make the tables complete.

We introduce different alphabets according to the rules of $P$ in the following way. These alphabets are versions of $V$ with different indexes: for the $i$th rule of $P$ we have alphabets $\{[X,i]\;\vert\;X\in V\}$ and $\{[X',i]\;\vert\;X\in V\}$. Moreover, we have some special additional symbols in the ETEG system in order to coordinate the derivation. These are $\{K,U,Z,Z'\}\cup \{[U',i]\;\vert\;1\leq i\leq r\}\cup \{[U,i]\;\vert\;1\leq ... ..._i=\emptyset\}\cup \{[\widehat{U},i]\;\vert\;1\leq i\leq r, Q_i\not=\emptyset\}$. By $K$ the derivation is blocked: if this symbol appears, then the derivation never results in a terminal word. The different versions of symbol $U$ allow the agent to work when $Q_i=\emptyset$.

First we show how a derivation step of $G$ can be simulated by $\Sigma$. During the simulation the sentential form has the form $wUZ$, where the word $w$ corresponds to the sentential form of $G$, and $U$ and $Z$ coordinate the simulation. Let us suppose that in a derivation step the rule $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i)$ is used for a sentential form $x$. The simulation in the ETEG system goes as follows.

In the first step the environment applies table $T_{i}$ to rewrite $xU$ into $[x,i][U, i]$ or into $[x,i][\widehat{U},i]$ depending on whether or not $Q_i=\emptyset$; the agent rewrites $Z$ into $Z'$. This is the only role of $Z$: it allows the agent to work during the first step of the simulation.

In the second step the agent applies the rule $[U,i]\ensuremath{\rightarrow}[U',i]$ if $Q_i=\emptyset$ or applies the rule $[A,i]\ensuremath{\rightarrow}[{A'},i]$ if $Q_i=\{A\}$. The environment rewrites the remaining letters by using table ${T'}_{i}$.

In the third simulation step the agent applies its rule corresponding to the rule of $G$, namely the rule $[{C'}_i,i]\ensuremath{\rightarrow}{\alpha}_i$, while the environment rewrites the remaining letters by using table ${T''}_{i}$. During this last step, the environment can delete the special symbols $Z'$ and $[U',i]$, thus allowing the possibility of finishing the derivation if the sentential form would be a terminal word.

Now we have showed that we can simulate the derivation steps of the random-context grammar. It follows from the construction of the simulating ETEG system that the behaviour described above is the only one which can result in a terminal word. The only possibility to start a derivation from a word over $V\cup\{U,Z\}$ is to use one of the tables $T_{i}$ and the rule $Z\ensuremath{\rightarrow}Z'$ of the agent. If the sentential form contains some forbidding letters from $R_i$, then the environment blocks the derivation in the next step by introducing a $K$; if the permitting symbol of the non-empty set $Q_i$ does not appear in the sentential form, the derivation is blocked because the agent cannot work. (It cannot use the other rule $[U,i]\ensuremath{\rightarrow}[{U'},i]$, because this symbol appears in the sentential form only if $Q_i=\emptyset$.) In the next step the agent has to use the rule $[{C'}_i,i]\ensuremath{\rightarrow}{\alpha}_i$ and the environment has to use table ${T''}_{i}$. These three consecutive steps simulate the application of one of the rules of $P$. height 5pt width 5pt depth 0pt

Using the fact that ${\mathcal{RC}}_{ac}^{\lambda}=\mathcal{RE}$ we obtain the following theorem:

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