Remarks on random-context grammars

Before starting to study the generative power of some variants of extended simple eco-grammar systems, we recall the notion of random-context grammars, which is used in the constructions of the chapter.

Definition 5.1  
A random-context grammar is a quadruple $G=(N, T, P, S)$ where $N$ is the finite set of non-terminals, $T$ is the finite set of terminals, $S\in {(N\cup T)}^+$ is the axiom, and $P$ is a finite set of random-context rules, that is, triplets in the form of $(C\ensuremath{\rightarrow}\alpha, Q, R)$, $C\ensuremath{\rightarrow}\alpha$ is a CF rule over $N\cup T$, where $C\in N$, and $Q$ and $R$ are sub-sets of $N$. For $x,y\in {(N\cup T)}^*$, we write $x\ensuremath{{\stackrel{\text{rc}}{\Longrightarrow}}_{}}y$ iff $x=x_1Cx_2$, $y=x_1\alpha x_2$ for some $x_1,x_2\in \ensuremath{{(N\cup T)}^*}$, $(C\ensuremath{\rightarrow}\alpha, Q, R)$ is a triplet in $P$, all symbols of $Q$ appear and no symbol of $R$ appears in $x_1x_2$ ($Q$ is called the permitting context, and $R$ is called the forbidding context of the rule $C\ensuremath{\rightarrow}\alpha$. If $Q$ and/or $R$ are empty, then no check is necessary.)

If the forbidding context is empty for every rule, then we speak about a random-context grammar without appearance checking, otherwise the grammar is with appearance checking.

In the dissertation all random-context grammars are with appearance checking, so for the sake of brevity sometimes we simply refer to a random-context grammar with appearance checking and with $\lambda$-rules as a random-context grammar.

We denote the transitive and reflexive closure of $\ensuremath{{\stackrel{\text{rc}}{\Longrightarrow}}_{}}$ by ${\ensuremath{{\stackrel{\text{rc}}{\Longrightarrow}}_{}}}^{*}$. The generated language of a random-context grammar consists of all the words which can be generated in some steps from axiom $S$.

Definition 5.2  
The generated language of a random-context grammar $G=(N, T, P, S)$ is the following:

$L(\Sigma)=\{\;v\in {T}^*\;\vert\;{S} {\ensuremath{{\stackrel{\text{rc}}{\Longrightarrow}}_{}}}^{*} v \}.$

The class of languages which can be generated by random-context grammars with appearance checking is denoted by ${\mathcal{RC}}_{ac}^{\lambda}$. It is well known (see [Dassow and PaunDassow and Paun1989]) that $\ensuremath{{\mathcal{RC}}_{ac}^{\lambda}}= \mathcal{RE}$, that is, all recursively enumerable languages can be generated by random-context grammars with appearance checking and with $\lambda$-rules.

Based on this result, we prove the universality of our models by simulating random-context grammars with different variants of simple eco-grammar systems. In these simulations we use another definition for random-context grammars, so first we show that the relation $\ensuremath{{\mathcal{RC}}_{ac}^{\lambda}}= \mathcal{RE}$ holds for this modified definition, too.

Informally speaking, in a random-context grammar we check the appearance of the permitting and the forbidding letters and if the result is positive (there are no forbidding letters in the sentential form and all the permitting ones are present), we apply the corresponding rule. In Definition 5.1 this check is done over $x_1x_2$, that is, the symbol which is about to be rewritten is left out. In such a way we can make such a requirement that the letter on the left-hand side of a rule appears at least twice in the current sentential form or that the left-hand side appears at most once.

Another possibility is to check the appearance of the symbols in the whole sentential form, this case is presented in the following definition.

Definition 5.3  
A random-context grammar with complete checking is a quadruple $G=(N, T,$ $P, S)$, where $N$, $T$,$S$, and $P$ are the same as in Definition 5.1. For $x,y\in {(N\cup T)}^*$, we write $x\ensuremath{{\stackrel{{\text{rc}_c}}{\Longrightarrow}}_{}}y$ iff $x=x_1Cx_2$, $y=x_1\alpha x_2$ for some $x_1,x_2\in \ensuremath{{(N\cup T)}^*}$, $(C\ensuremath{\rightarrow}\alpha, Q, R)$ is a triplet in $P$, all symbols of $Q$ appear and no symbol of $R$ appears in $x_1Cx_2$.

The generated language is defined as in Definition 5.2.

Definition 5.4  
The generated language of a random-context grammar with complete checking $G=(N, T, P, S)$ is the following:

$L(\Sigma)=\{\;v\in {T}^*\;\vert\;{S} {\ensuremath{{\stackrel{{\text{rc}_c}}{\Longrightarrow}}_{}}}^{*} v \}.$

Here we denote the transitive and reflexive closure of $\ensuremath{{\stackrel{{\text{rc}_c}}{\Longrightarrow}}_{}}$ by ${\ensuremath{{\stackrel{{\text{rc}_c}}{\Longrightarrow}}_{}}}^{*}$.


In the following we present two auxiliary statements which make it possible to suppose that a random-context grammar has some special properties. These statements are mentioned in several places in the literature, for example in [Dassow and PaunDassow and Paun1989], but without proof. Therefore we decided to present the proofs here.

The first lemma shows that all the languages which can be generated by random-context grammars working according to Definition 5.1, can also be generated by random-context grammars with complete checking, that is, by random-context grammars working according to Definition 5.3.

In the following, for the sake of simplicity, when a set contains only one element, $C$, for the set we use the notation $C$ instead of the notation $\{C\}$.

Lemma 5.5  
For any random-context grammar $G=(N, T, P, S)$ we can construct a random-context grammar with complete checking $\ensuremath{{{\overline{G}}}}=(\ensuremath{{{\overline{N}}}},\ensuremath{{{\overline{T}}}}, \ensuremath{{{\overline{P}}}}, \ensuremath{{{\overline{S}}}})$, such that $L(G)=L(\ensuremath{{{\overline{G}}}})$.

PROOF.
We denote by $r$ the number of rules in $P$. The rules of $P$ are enumerated as $p_i=(C_i\ensuremath{\rightarrow}{\alpha}_i,Q_i,R_i)$. We refer to the components of the $i$th rule as $C_i$, ${\alpha}_i$, $Q_i$, and $R_i$.

Let the components of $\ensuremath{{{\overline{G}}}}$ be the following:

$\ensuremath{{{\overline{T}}}}=T$,
$\ensuremath{{{\overline{S}}}}=S$,
$\ensuremath{{{\overline{N}}}}=N\cup \{\;\ensuremath{{{\overline{C_j}}}}\;\vert\;1\leq j\leq r\;\}.$

For any $i$ ( $1\leq i\leq r$), there are some rules in $\ensuremath{{{\overline{P}}}}$ according to the $i$th rule of $P$ in the following way:

• if for the $i$th rule of $P$, $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i)$, both $C_i\in Q_i$ and $C_i\in R_i$ hold, then we do not put any rule into $\ensuremath{{{\overline{P}}}}$, because a rule like this is never applied in $G$;
• if for the $i$th rule of $P$, $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i)$, neither $C_i\in Q_i$ nor $C_i\in R_i$ holds, then we put $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i\cup \{\;\ensuremath{{{\overline{C_j}}}}\;\vert\;1\leq j\leq n\;\})$ into $\ensuremath{{{\overline{P}}}}$;
• if for the $i$th rule of $P$, $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i)$, $C_i\in Q_i$ holds but $C_i\in R_i$ does not hold, then we put two rules into $\ensuremath{{{\overline{P}}}}$: $(C_i\ensuremath{\rightarrow}{\ensuremath{{{\overline{C_i}}}}}, Q_i\setminus\{C_i\}, R_i\cup \{\;\ensuremath{{{\overline{C_j}}}}\;\vert\;1\leq j\leq n\;\})$ and $(\ensuremath{{{\overline{C_i}}}}\ensuremath{\rightarrow}{\alpha}_i, C_i,\{\;\ensuremath{{{\overline{C_j}}}}\;\vert\;1\leq j\leq n, i\not =j\;\})$;
• if for the $i$th rule of $P$, $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i)$, $C_i\in Q_i$ does not hold but $C_i\in R_i$ does, then we put the following two rules into $\ensuremath{{{\overline{P}}}}$: $(C_i\ensuremath{\rightarrow}{\ensuremath{{{\overline{C_i}}}}}, Q_i, (R_i\setmi... ...\{\;C_i\;\})\cup \{\;\ensuremath{{{\overline{C_j}}}}\;\vert\;1\leq j\leq n\;\})$ and $(\ensuremath{{{\overline{C_i}}}}\ensuremath{\rightarrow}{\alpha}_i, \emptyset,... ...\}\cup\{\;\ensuremath{{{\overline{C_j}}}}\;\vert\; 1\leq j\leq n, i\not =j\;\})$.

It follows directly from the construction of $\ensuremath{{{\overline{P}}}}$ that $L(\ensuremath{{{\overline{G}}}})=L(G)$, since $\ensuremath{{{\overline{G}}}}$ works according to Definition 5.3 and $G$ works according to Definition 5.1. The main idea is that if $C_i\in Q_i$ or $C_i\in R_i$ holds for a rule of $P$, then we check the appearance of the symbols in two steps. The additional symbols $\ensuremath{{{\overline{C_j}}}}$ are used to prevent the grammar $\ensuremath{{{\overline{G}}}}$ from starting to simulate a rule of $P$ while another rule of $P$ is being simulated. height 5pt width 5pt depth 0pt

Let us note here that the construction of $\ensuremath{{{\overline{P}}}}$ presented above gives that we can suppose that $C_i\not \in Q_i$, $C_i\not \in R_i$, and $R_i\cap Q_i=\emptyset$ hold for the rules $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i)$ of $\ensuremath{{{\overline{P}}}}$.

By the following lemma, we can suppose that both the permitting and the forbidding contexts of the rules of a random-context grammar with complete checking (that is, working according to Definition 5.3) contain at most one symbol.

Lemma 5.6  
For any random-context grammar with complete checking $G=(N, T, P, S)$ we can construct another random-context grammar with complete checking $\ensuremath{{{\overline{G}}}}=(\ensuremath{{{\overline{N}}}},\ensuremath{{{\overline{T}}}}, \ensuremath{{{\overline{P}}}}, \ensuremath{{{\overline{S}}}})$, such that $L(G)=L(\ensuremath{{{\overline{G}}}})$, $\vert Q\vert\leq 1$ and $\vert R\vert\leq 1$ hold for all the rules $(C\ensuremath{\rightarrow}\alpha, Q, R)\in \ensuremath{{{\overline{P}}}}$.

PROOF.
As in Lemma 5.5, we denote by $r$ the number of rules in $P$. The rules of $P$ are enumerated as $p_i=(C_i\ensuremath{\rightarrow}{\alpha}_i,Q_i,R_i)$ and we also use the notations $Q_i=\{\;A_{i,1},\ldots, A_{i,k_i}\;\}$, where $k_i=\vert Q_i\vert$ and $R_i=\{\;B_{i,1},\ldots, B_{i, {\ell}_i}\;\}$, where ${\ell}_i=\vert R_i\vert$. We will refer to the components of the $i$th rule as $C_i$, ${\alpha}_i$, $Q_i$, $R_i$ and to the members of $Q_i$ and $R_i$ as $A_{i,s}$, $B_{i,t}$, $1\leq s\leq k_i$, $1\leq t\leq {\ell}_i$.

Let the components of $\ensuremath{{{\overline{G}}}}$ be the following:

$\ensuremath{{{\overline{T}}}}=T$,
$\ensuremath{{{\overline{S}}}}=SS_0$,
$\ensuremath{{{\overline{N}}}}=N\cup \{\;\ensuremath{{{\overline{C_j}}}}\;\vert... ...}\cup \{\; S_0, S_i^j\;\vert\; 1\leq i\leq r, 0\leq j\leq k_i+{\ell}_i+1 \;\}.$

The set $\ensuremath{{{\overline{P}}}}$ is defined as follows. For each rule $(C_i\ensuremath{\rightarrow}{\alpha}_i, \{A_{i,1}, \ldots, A_{i,k_i}\},$ $\{B_{i,1}, \ldots, B_{i,{\ell}_i}\})$ of $P$ ($k_i=\vert Q_i\vert$, ${\ell}_i=\vert R_i\vert$) we put the following $3+k_i+{\ell}_i+2$ rules into $\ensuremath{{{\overline{P}}}}$:

• $(S_0\ensuremath{\rightarrow}S_i^0, \emptyset, \emptyset)$,
• $(C_i\ensuremath{\rightarrow}\ensuremath{{{\overline{C_i}}}}, S_i^0, \ensuremath{{{\overline{C_i}}}})$,
• $(S_i^0\ensuremath{\rightarrow}S_i^1, \ensuremath{{{\overline{C_i}}}}, \emptyset)$,
• $(S_i^{s}\ensuremath{\rightarrow}S_i^{s+1}, A_{i,s}, \emptyset)$ for $1\leq s\leq k_i$,
• $(S_i^{k_i+t}\ensuremath{\rightarrow}S_i^{k_i+t+1}, \emptyset, B_{i,t})$ for $1\leq t\leq {\ell}_i$,
• $(\ensuremath{{{\overline{C_i}}}}\ensuremath{\rightarrow}{\alpha}_i, S_i^{k_i+{\ell}_i+1}, \emptyset)$, and
• $(S_i^{k_i+{\ell}_i+1}\ensuremath{\rightarrow}S_0, \emptyset, \ensuremath{{{\overline{C_i}}}})$.

Moreover, we also put the rule $(S_0\ensuremath{\rightarrow}\lambda, \emptyset, \emptyset)$ into $\ensuremath{{{\overline{P}}}}$.

All the rules of $P$ can be simulated by the corresponding $k_i+{\ell}_i+5$ rules of $\ensuremath{{{\overline{P}}}}$: first we check the appearance of symbols in $Q_i$, then the non-appearance of symbols in $R_i$. Thus $L(G)\subseteq L(\ensuremath{{{\overline{G}}}})$. On the other hand, it follows from the construction that the rules of $\ensuremath{{{\overline{P}}}}$ which correspond to the same rule of $P$, must be used together, one after the other, in the same order as explained above. The forbidding context of the second rule prevents the grammar $\ensuremath{{{\overline{G}}}}$ from starting the simulation of the same rule more than once. Two different rules cannot be simulated at the same time because only one symbol $S$ is in the sentential form and its index determines the rule to be simulated. This gives $L(\ensuremath{{{\overline{G}}}})\subseteq L(G)$. height 5pt width 5pt depth 0pt

We note here, that like in Lemma 5.5, $C_i\not \in Q_i$, $C_i\not \in R_i$, and $R_i\cap Q_i=\emptyset$ hold for the rules $(C_i\ensuremath{\rightarrow}{\alpha}_i, Q_i,R_i)$ of $\ensuremath{{{\overline{P}}}}$.

The two lemmas together with the result $\ensuremath{{\mathcal{RC}}_{ac}^{\lambda}}= \mathcal{RE}$ gives that any recursively enumerable language can be generated by a random-context grammar which uses complete checking and whose permitting and forbidding contexts contain at most one symbol.