Simple eco-grammar systems of type INS and REP

Simple eco-grammar systems with only INS- or with only REP-type agents are special cases of hybrid eco-grammar systems. In this part of the chapter we present some results about these homogeneous systems. The first results are almost direct consequences of the results presented in the first part of the chapter, we present them however again, because we find it worth showing the similarity between them and the results presented in Section 3.1.

Definition 4.13  
A simple eco-grammar system of type INS is a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$ where $n_1=n$. A simple eco-grammar system of type REP is a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$ where $n_1=0$.

Since in simple eco-grammar systems of type INS or REP the value of $n_1$ is determined by the type of the system, we omit it in the notation and thus a simple eco-grammar system of type INS or REP is denoted by .

Those simple eco-grammar systems, where the agents are represented by sets of CF rules will be referred as EG systems of type CF in this section.

We want to define the derivation mode $=k$ $(1\leq k\leq n)$ for simple eco-grammar systems of type INS and REP in the similar way as it was presented in the CF case. We do not have to introduce this derivation mode as a new one, because we can consider it as a special case of Definition 4.3. In this way the same derivation mode is defined as in Definition 3.1 for simple eco-grammar systems of type CF.

Definition 4.14  
Consider a simple eco-grammar system of type INS. We say that $x$ directly derives $y$ in $\Sigma$ in the derivation mode $=k$ (with $x,y\in {V_E}^*$, $1\leq k\leq n$, written as $x\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}y$), if $x\ensuremath{\stackrel{=k,=0}{{\Longrightarrow}_{\ensuremath{{{\overline{\Sigma}}}}}}}y$ holds with the hybrid eco-grammar system $\ensuremath{{{\overline{\Sigma}}}}=(\:V_E,P_E,n,R_1,\ldots,R_n,\omega)$.

Similarly:

Definition 4.15  
Consider a simple eco-grammar system of type REP. We say that $x$ directly derives $y$ in $\Sigma$ in the derivation mode $=k$ (with $x,y\in {V_E}^*$, $1\leq k\leq n)$, written as $x\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}y$), if $x\ensuremath{\stackrel{=0,=k}{{\Longrightarrow}_{\ensuremath{{{\overline{\Sigma}}}}}}}y$ holds with the hybrid eco-grammar system $\ensuremath{{{\overline{\Sigma}}}}=(\:V_E,P_E,0,R_1,\ldots,R_n,\omega)$.

We denote the transitive and reflexive closure of $\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}$ by $\ensuremath{\stackrel{=k} {{\Longrightarrow}_{\Sigma}^{*}}}$.

Definition 4.16  
Consider a simple eco-grammar system of type $X$ $(X\in \{$INS$,$REP$\})$. The generated language in the derivation mode $=k$ is the following:

$$L(\Sigma,=k)=\{ v\in \ensuremath{{V_E}^*}\vert\;{\omega}\ensuremath{\stackrel{=k} {{\Longrightarrow}_{\Sigma}^{*}}}v \}$$

As already presented in Section 4.1, the class of languages which can be generated by a simple eco-grammar system of type $X$ is denoted by $\mathcal{L}(E_X)$ for $X\in \{$CF$,$INS$,$REP$\}$. The class of languages generated by systems containing $n$ agents and operating in the derivation mode $=k$ is denoted by $\mathcal{L}(E_X(n,=k))$ for $X\in \{$CF$,$INS$,$REP$\}$.

In the following we summarise some consequences of Theorem 4.11. In these results language classes $\mathcal{L}(E_X(n,=k))$ with fixed $X$ ( $X\in \{$INS$,$REP$\}$) and with different parameters $k$ and $n$, with $1\leq k\leq n$, are compared. We can see that the results are similar to the ones presented in Chapter 3 about EG systems of type CF.

To begin with, results concerning simple eco-grammar systems of type INS are presented.

Theorem 4.17  
For $1\leq k\leq n$ and $1\leq \ell\leq m$

1. $\mathcal{L}(E_{INS}(n,=k))\subset \mathcal{L}(E_{INS}(m,=k))$ if $k\geq 2$ and $m>n$,
2. $\mathcal{L}(E_{INS}(n,=1))=\mathcal{L}(E_{INS}(m,=1))$,
3. otherwise $\mathcal{L}(E_{INS}(n,=k))$ and $\mathcal{L}(E_{INS}(m,=\ell))$ are incomparable.

PROOF.
These statements are corollaries of Theorem 4.11. The equality and the inclusions are true because $\mathcal{L}(E_H(n,=k_1,=0))\subset \mathcal{L}(E_H(m,=k_1,=0))$ holds for $m\geq n\geq k_1\geq 2$, $\mathcal{L}(E_H(n,=1,=0))=\mathcal{L}(E_H(m,=1,=0))$ holds for $n,m\geq 1$ and because for each hybrid eco-grammar system working in the derivation mode $(=k_1, =0)$ there exists another hybrid eco-grammar system containing the same number of agents, all of which are of type INS, working also in the derivation mode $(=k_1, =0)$ and generating the same language.

The incomparability also follows from the incomparability results of Theorem 4.11 and from the above fact that we can suppose that in a hybrid eco-grammar system working in the derivation mode $(=k_1, =0)$ there are only INS-type agents.height 5pt width 5pt depth 0pt

About simple eco-grammar systems of type REP we have similar results.

Theorem 4.18  
For $1\leq k\leq n$ and $1\leq \ell\leq m$

1. $\mathcal{L}(E_{REP}(n,=k))\subset \mathcal{L}(E_{REP}(m,=k))$ if $k\geq 2$ and $m>n$,
2. $\mathcal{L}(E_{REP}(n,=1))=\mathcal{L}(E_{REP}(m,=1))$,
3. otherwise $\mathcal{L}(E_{REP}(n,=k))$ and $\mathcal{L}(E_{REP}(m,=\ell))$ are incomparable.

PROOF.
These statements follow also from Theorem 4.11. Here we have to use the results in the case $(=0,=k_2)$ and the fact that we can suppose that in a hybrid eco-grammar system working in the derivation mode $(=k_1, =0)$ there are only REP-type agents.height 5pt width 5pt depth 0pt

In the following, we compare the language classes $\mathcal{L}(E_{CF})$, $\mathcal{L}(E_{INS})$, $\mathcal{L}(E_{REP})$ and prove that they are pairwise incomparables.

Lemma 4.19  
$\mathcal{L}(E_{INS})$ and $\mathcal{L}(E_{REP})$ are incomparables.

PROOF.
The languages $L=\{\:a,b^2\:\}$ and $L_{REP}(=1)$ (for the definition see part 4 of Theorem 4.11) proves the incomparability by the same reason as in part 4 of Theorem 4.10 and 4.11. height 5pt width 5pt depth 0pt

For the incomparability results concerning $\mathcal{L}(E_{CF})$, we need some special languages. They have a structure similar to the one presented in Example 4.5 but they have some new features as well.

Example 4.20  
Let be the following simple eco-grammar system of type INS for $1\leq k\leq n$:

• $V_E=\{a_1,b_1,a_2,b_2,c_1,\ldots,c_n\}$,
• $P_E=\{b_1\ensuremath{\rightarrow}{b_2}, a_1\ensuremath{\rightarrow}{a_2},b_2\e... ...ow}{a_1} \} \cup \:{\bigcup}_{1\leq j \leq n}\{c_j\ensuremath{\rightarrow}a_1\}$,
• $R_i=\{(b_1,c_i,a_1),(b_2,a_1,a_2)\}$ for $1\leq i \leq n$,
• $w={a_1}b_1{a_1}^{k}$.

Having examined the system and the derivation process, we can see that in the derivation mode $=k$, after $2i$ ($i\geq 0$) derivation steps we have the word ${a_1}^{}b_1{a_1}^{k+2ik}$; after $2i+1$ ($i\geq 0$) derivation steps the sentential form is in the form of ${a_2}b_2{[c_{i_1},c_{i_2},\ldots,c_{i_k}, {{a_2},{a_2},\ldots,{a_2}}]}^Pa_2$, where the letters $c$ are different.

Requirements of Lemma 4.8 hold for the generated language $L_{INS}(n,=k):=L(\Sigma,k)$ and we note that in the words being over the second sub-alphabet $\{a_2,b_2,c_1,\ldots,c_n\}$ the only letter $b_2$ precedes all occurrences of the letters $c$. We also note that the distance between $b_2$ and the letters $c$ is not bounded in the words over $\{a_2,b_2,c_1,\ldots,c_n\}$, that is, for any $M_0>0$ there exists a word over this sub-alphabet where the sub-word between $b_2$ and the first letter $c$ is longer than $M_0$.

Lemma 4.21  
For $1\leq k\leq n$

$$L_{INS}(n,=k)\in \mathcal{L}(E_{INS}(n,=k))\setminus \mathcal{L}(E_{CF}).$$

PROOF.
Since $L_{INS}(n,=k)$ (defined above in Example 4.20) has the properties required by Lemma 4.8, if $L_{INS}(n,=k)=L(\Sigma, =\ell)$ with a simple eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots,} \ensuremath{R_m,\omega\:)}$ of type CF, then in each derivation sequence words over alph$(L_1)=\{a_1,b_1\}$ are followed by words over alph$(L_2)=\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}$, and conversely.

We examine how the system $\Sigma$ can introduce letters $c$ during a derivation step $v_1\ensuremath{{\Rightarrow}_{\Sigma}}v_2$ where $v\in {\{a_1,b_1\} }^*$ and $v_2\in {\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}}^*$.

• $P_E$ cannot introduce letters $c$ because in this case more than $k$ letters $c$ could occur in the words of $L(\Sigma)$.
• For any $i$, $1\leq i \leq n$ there must be in $\Sigma$ at least one agent-rule in the form of $a_1\ensuremath{\rightarrow}\alpha c_i\beta$ with $\alpha, \beta\in {(\text{alph}(L_2))}^*$ because if there is a letter $c_i$ which can be derived only from $b_1$, then this letter $c_i$ could not occur at distance of any length from the beginning of the word (considering that the position of $b_1$ is fixed).
• In $P_E$ there must be at least one rule in the form of $a_1\ensuremath{\rightarrow}u$, with $u\not=\lambda$, otherwise the lengths of the words in $L_2$ would be bounded.
• For any agent-rule being in the form of $a_1\ensuremath{\rightarrow}\alpha c_i\beta$, it follows that ${\vert\alpha\vert}_{b_2}=0$ holds. Otherwise, by applying this rule to the last letter $a_1$ of a long word in $L_1$ and by applying a $P_E$ rule in the from of $a_1\ensuremath{\rightarrow}u$, $u\in {(\text{alph}(L_2))}^+$ to all the other letters which are not concerned by the actions of the agents, we would get a word where $b_2$ is not standing at the second position of the word.

  So we have ${\vert\alpha\vert}_{b_2}=0$. But we can also apply this rule $a_1\ensuremath{\rightarrow}\alpha c_i\beta$ to the first letter $a_1$ of a word in $L_1$ and so we would get a word where a letter $c_i$ stands before $b_2$. It is a contradiction because there are no words like this in $L_{INS}(n,=k)$.

height 5pt width 5pt depth 0pt

Example 4.22  
Let be the following simple eco-grammar system of type CF for $1\leq k\leq n$:

• $V_E=\{a_1,b_1,a_2,b_2,c_1,\ldots,c_n\}$,
• $P_E=\{b_1\ensuremath{\rightarrow}{b_2}^2, a_1\ensuremath{\rightarrow}{a_2}^2,b... ...}{a_1}^2 \} \cup \:{\bigcup}_{1\leq j \leq n}\{c_j\ensuremath{\rightarrow}a_1\}$,
• $R_i=\{a_1\ensuremath{\rightarrow}c_i,c_i\ensuremath{\rightarrow}a_1\}$ for $1\leq i \leq n$,
• $w=b_1{a_1}^{1+k}$.

In the derivation mode $=k$, after $2s$ ($s\geq 0$) derivation steps we have the word ${b_1}^{4^s}{a_1}^{4^s+k}$; after $2s+1$ ($s\geq 0$) derivation steps we have a word in the form of ${b_2}^{2\cdot 4^s} {[c_{j_1},c_{j_2},\ldots, c_{j_k}, {a_2}^2,{a_2}^2,\ldots,{a_2}^2]}^P$ (in the latter formula the letters $c$ are different).

The requirements of Lemma 4.7 holds for the generated language $L_{CF}(n,=k):=L(\Sigma, =k)$ and we note that in the words being over the second sub-alphabet $\{a_2,b_2,c_1,\ldots,c_n\}$ the letters $c$ can occur anywhere after the sequence of letters $b$.

Lemma 4.23  
For $1\leq k\leq n$

$$L_{CF}(n,=k)\in \mathcal{L}(E_{CF}(n,= k))\setminus \mathcal{L}(E_{INS}).$$

PROOF.
Let us suppose that $L_{CF}(n,=k)=L(\Sigma,=\ell)$ with a simple eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots,} \ensuremath{R_m,\omega\:)}$ of type INS (where $L_{CF}(n,=k)$ is defined in Example 4.22 above).

As mentioned above, $L_{CF}(n,=k)$ has all the properties required by Lemma 4.7, therefore we can say that if $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ holds, then $u$ and $v$ are over the different sub-alphabets $\{\;b_1,a_1\;\}$ and $\{\; b_2,a_2, c_1,\ldots, c_n\;\}$.

We examine the rules of $P_E$ which can be used to generate words in $L_{CF}(n,=k)\cap {\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}}^*$ from words being over $\{a_1,b_1\}$. These rules are in the form of $a_1\ensuremath{\rightarrow}\alpha$ or $b_1\ensuremath{\rightarrow}\beta$, where $\alpha, \beta\in {\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}}^*$.

• Neither $\alpha$ nor $\beta$ can contain letters $c$ because in this case more than $k$ letters $c$ could stand in some generated words.
• Neither $\alpha$ nor $\beta$ can contain letters $a_2$ and $b_2$ together because in this case we would be able to derive words with mixed letters $a_2$ and $b_2$.
• $\alpha$ cannot be in the form of ${{b_2}}^i$, where $i\geq 1$ and $\beta$ cannot be in the form of ${a_2}^j$, where $j\geq 1$ because in these cases $b_2$ could stand in the last or $a_2$ could stand in the first position of a word in the generated language.
• Thus $\alpha={a_2}^i$ and $\beta={b_2}^j$, $i,j\geq 0$. Moreover, there must be at least one rule with $i,j\geq 1$, otherwise the number of letters $a_2$ and $b_2$ would be bounded in the generated words.

We have seen that only agents can introduce letters $c$ during a derivation, so the rules which can introduce letters $c$ are insertion rules and are in one of the following forms (see the words of $L_{CF}(n,=k)\cap {\{a_1,b_1\}}^*$):

(1) $({b_1}^{i_1}{a_1}^{i_2},\gamma c_i\delta,{a_1}^{i_3})$

(2) $({b_1}^{i_1},\gamma c_i\delta,{b_1}^{i_2})$

(3) $({b_1}^{i_1},\gamma c_i\delta,{b_1}^{i_2}{a_1}^{i_3})$

(4) $({b_1}^{i_1},\gamma c_i\delta,{a_1}^{i_2})$

(5) $({a_1}^{i_1},\gamma c_i\delta,{a_1}^{i_2})$

where $i_1,i_2,i_3\geq 1$ and $\gamma,\delta\in {\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}}^*$.

In the cases (2), (3) and (4), a letter $c_i$ could stand before letters $b_2$ if we use the rule $b_1\ensuremath{\rightarrow}{b_2}^j$, $j\geq 1$, of $P_E$.

So all the rules producing letters $c$ must be in the form of (1) or (5) but from this fact it follows that $P_E$ must contain a deletion rule in the form of $a_1\ensuremath{\rightarrow}\lambda$ because this is the only way to introduce a letter $c$ just after the sequence of letters $b$. If there exists a deletion rule in $P_E$ in the form of $a_1\ensuremath{\rightarrow}\lambda$, then from a word long enough, being over alph$(L_1)$, we could derive a word which would contain a lot of letters $b_2$ but only a few letters $a_2$ (by using this deletion rule and the rule $b_1\ensuremath{\rightarrow}{b_2}^j$, $j\geq 1$ at the same step). It is a contradiction because in $L_{CF}(n,=k)$, in each word, the number of letters $a_2$ is at least the half of the number of letters $b_2$.height 5pt width 5pt depth 0pt

Example 4.24  
Let be the following simple eco-grammar system of type REP for $2\leq k\leq n$:

• $V_E=\{a_1,a_2,c_1,\ldots,c_n\}$,
• $P_E=\{ a_1\ensuremath{\rightarrow}{a_2}^2,a_2\ensuremath{\rightarrow}{a_1}^2 \} \cup \:{\bigcup}_{1\leq j \leq n}\{c_j\ensuremath{\rightarrow}a_1\}$,
• $R_i=\{(a_1,a_1,a_1)\ensuremath{\rightarrow}(a_1,c_i,a_1)\}$
  $\cup \left\{(e,c_i,f)\ensuremath{\rightarrow}(e,a_1,f)\vert e,f\in \{a_1, c_1, \ldots,c_n\}\right\}$ for $1\leq i \leq n$,
• $w={a_1}^{2+k}$.

In mode $=k$, the generated language $L_{REP}(n,=k):=L(\Sigma,=k)$ contains words in the form of ${a_1}^{2\cdot 4^i+k}$ or $a_2[c_{i_1}, \ldots, c_{i_k}, a_2,\ldots, a_2]^Pa_2$ and satisfies the requirements of Lemma 4.8. In each word over the second sub-alphabet $\{a_2,c_1,\ldots,c_n\}$ the letters $c$ can occur anywhere except the first and the last position.

Example 4.25  
Let be the following simple eco-grammar system of type REP:

• $V_E=\{a_1,a_2,b_1,b_2,c_1,\ldots,c_n\}$,
• $P_E=\{ a_1\ensuremath{\rightarrow}{a_2}^2,a_2\ensuremath{\rightarrow}{a_1}^2,b... ...}{b_1}^2 \} \cup \:{\bigcup}_{1\leq j \leq n}\{c_j\ensuremath{\rightarrow}a_1\}$,
• $R_i=\{(b_1,a_1,a_1)\ensuremath{\rightarrow}(b_1,c_i,a_1)\}\cup \{(b_2,c_i,a_2)\ensuremath{\rightarrow}(b_2,a_1,a_2)\}$
  for $1\leq i \leq n$,
• $w=b_1a_1a_1$.

The first few steps of a derivation in derivation mode $=1$ can be the following:

$$b_1a_1a_1\ensuremath{\stackrel{=1}{{\Longrightarrow}_{\Sigma}}}{b... ..._2}^8c_{i_2}{a_2}^8\ensuremath{\stackrel{=1}{{\Longrightarrow}_{\Sigma}}}\cdots$$

Hence,

$$L_R(n,=1):=L(\Sigma,=1)=\{{b_1}^{4^s}a_1{a_1}^{4^s}\vert\;1\leq s\}\cup \{{b_2}^{2\cdot4^s}c_i{a_2}^{2\cdot4^s}\vert\;1\leq s,1\leq i\leq n\}$$

The generated language $L_R(n,=1)$ satisfies requirements of Lemma 4.8 and the letters $c$ can occur only between the sequence of letters $b_2$ and $a_2$ in the words being over $\{a_2,b_2,c_1,\ldots,c_n\}$.

Lemma 4.26  

1. For $2\leq k\leq n$ $L_{REP}(n,=k)\in \mathcal{L}(E_{REP}(n,=k))\setminus \mathcal{L}(E_{CF})$.
2. For $1\leq n$ $L_R(n,=1)\in \mathcal{L}(E_{REP}(n,=1))\setminus\mathcal{L}(E_{CF})$.

PROOF.
1.
Suppose that $L_{REP}(n,=k)=L(\Sigma,=\ell)$ holds with a simple eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots,} \ensuremath{R_m,\omega\:)}$ of type CF (where $L_{REP}(n,=k)$ is defined in Example 4.24 above).

First, we note that letters $c$ can be introduced only by agents, otherwise more than $k$ letters $c$ could be in the generated words. Hence letters $c$ can be introduced only by the agent-rules being in the form of $a_1\ensuremath{\rightarrow}\alpha c_i\beta$, where $\alpha, \beta\in {\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}}^*$ (since we can apply Lemma 4.8 to $L_{REP}(n,=k)$ with alph$(L_1)=\{a_1\}$).

Since $k\geq 2$, there exist two different letters $c$ in $V_E$, $c_1$ and $c_2$, and these letters can occur at distance of any length from each other in the words of $L_{REP}(n,=k)$. Therefore $\ell=1$ is not possible. Since $\ell\geq 2$, for each letter $c$ there exists at most one agent which can introduce this letter $c$, otherwise words with two letters $c$ with the same subscript could be generated.

One agent could not introduce two different letters $c$ either because in this case the distance between these letters $c$ would be bounded in the generated words.

Thus in an agent-rule in the form of $a_1\ensuremath{\rightarrow}\alpha c_i\beta$ $(1\leq i\leq m)$ $\alpha$ cannot contain a letter $c$, therefore $\alpha={a_2}^j$, $j\geq 0$. Moreover, $j=0$ is not possible because in this case a letter $c_i$ could stand at the first position of a generated word (by applying this agent-rule to the first letter of a word).

Hence we obtain that any rule, used by the agents to introduce letters $c$, is in the form of $a_1\ensuremath{\rightarrow}{a_2}^jc_i\beta$, $j\geq 1$ and $\beta\in {\{a_2\}}^*$. But in this case words like $xc_ic_jy$ ( $x,y\in {\ensuremath{\{a_2,c_1,\ldots,c_n\}}}^*)$ are impossible to derive, which is a contradiction.

2.
Let us suppose that $L_{R}(n,=1)=L(\Sigma,=\ell)$ holds with a simple eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots,} \ensuremath{R_m,\omega\:)}$ of type CF (where $L_{R}(n,=1)$ is defined in Example 4.25 above). We can apply Lemma 4.8 to $L_R(n,=1)$, so the words in a derivation sequence are alternately over $\{a_1,b_1\}$ and $\{a_2,b_2,c_1,\ldots,c_n\}$. Following the line of the proof of Lemma 4.23, we can say that the rules of $P_E$ used to produce words being over the sub-alphabet $\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}$ are either in the form $a_1\ensuremath{\rightarrow}{a_2}^j$ or in the form $b_1\ensuremath{\rightarrow}{b_2}^i$, where $i,j\geq 0$. We can also say that there are rules of the above form with $i,j\geq 1$.

The agents can introduce letters $c$ only by rules in the form of $a_1\ensuremath{\rightarrow}\alpha c_i\beta$ or $b_1\ensuremath{\rightarrow}\alpha c_i\beta$, where $\alpha, \beta\in {\ensuremath{\{a_2,b_2,c_1,\ldots,c_n\}}}^*$. By applying a rule $b_1\ensuremath{\rightarrow}\alpha c_i\beta$ to the first $b_1$ of a word of $L_1=L_R(n,=1)\cap {\{a_1,b_1\}}^*$ and the rule $b_1\ensuremath{\rightarrow}{b_2}^j$, $j\geq 1$ to all other letters $b_1$ which are not concerned by the actions of the agents, we obtain a word where a letter $c$ stands before a letter $b_2$. Similarly, by applying a rule $a_1\ensuremath{\rightarrow}\alpha c_i\beta$ to the last letter $a_1$ and the rule $a_1\ensuremath{\rightarrow}{a_2}^i$, with $i\geq 1$, to the remaining letters $a_1$, we get a word where a letter $c$ is after a letter $a_2$. In both cases we generate a word which is not in $L_{R}(n,=1)$.height 5pt width 5pt depth 0pt

Example 4.27  
Let be the following simple eco-grammar system of type CF for $1\leq k\leq n$:

• $V_E=\{a_1,a_2,c_1,\ldots,c_n\}$,
• $P_E=\{a_1\ensuremath{\rightarrow}{a_2},a_2\ensuremath{\rightarrow}{a_1} \} \cup\:{\bigcup}_{1\leq i \leq n}\{c_i\ensuremath{\rightarrow}a_1\}$,
• $R_i=\{a_1\ensuremath{\rightarrow}{c_i}^2,c_i\ensuremath{\rightarrow}a_1\}$, for $1\leq i \leq n$,
• $w={a_1}^{k}$.

The generated language $L_{n,=k}:=L(\Sigma,=k)$ in the derivation mode $=k$ contains two types of words: ${a_1}^{+}$ and ${[{c_{i_1}}^2,{c_{i_2}}^2,\ldots, {c_{i_k}}^2, {{a_2},{a_2},\ldots,{a_2}}]}^P$, with different letters $c$. The generated language has the properties required in Lemma 4.7.

Lemma 4.28  
For $1\leq k\leq n$

$$L_{n,=k}\in \mathcal{L}(E_{CF}(n,=k))\setminus \mathcal{L}(E_{REP}).$$

PROOF.
If $L_{n,=k}=L({\Sigma},=\ell)$ holds with an eco-grammar system $\Sigma=(\:V_E,P_E,R_1,\ldots,$ $R_m,\omega\:)$ of type REP (where $L_{n,=k}$ is defined in Example 4.27 above), then the words over $\ensuremath{\{a_2,c_1,\ldots,c_n\}}$ are derived in ${\Sigma}$ from words over $\{a_1\}$ (since we can apply Lemma 4.7 for $L_{n,=k}$). Moreover, similarly to the previous proofs, we can say that only agents can introduce letters $c$. Since each agent can introduce at most one letter $c$, ${\Sigma}$ has to have for each $1\leq i \leq n$ at least two agents which can introduce the same letter $c_i$ and $\ell\geq 2$ must hold as well.

These $c_i$-producing agent-rules must be in the form of $(a_1,a_1,a_1)\ensuremath{\rightarrow}(a_1,c_i,a_1)$ but in this way we cannot guarantee that they are applied at neighbouring positions, thus we could also derive words with separated letters $c_i$.height 5pt width 5pt depth 0pt

The consequence of the above lemmas is the following theorem:

Theorem 4.29  
Language classes $\mathcal{L}(E_{INS})$, $\mathcal{L}(E_{REP})$, and $\mathcal{L}(E_{CF})$ are pairwise incomparable.

PROOF.
It is a direct consequence of Lemma 4.19,  4.21, 4.23, 4.26, and 4.28.height 5pt width 5pt depth 0pt