Generative power and classification of matrix grammars

Question

[Edited] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy.

In here it is stated that:

• A matrix grammar is a quintuple $G = (N, T, M, S, F)$, where $N,T$, and $S$ are specified as for a context-free grammar, $M = \{m_1, m_2, \dots m_n \}$ is a finite set of finite sequences of context free rules (i.e. for $1 \leq m_1 \leq n$, $m_i = (A_{i,1} \rightarrow w_{i,1}, A_{i,2} \rightarrow w_{i,2}, \dots A_{i,r_i} \rightarrow w_{i,r_i})$ for some $r_i \geq 1$, $A_{i,j} \in N$, $w_{i,j} \in (N \cup T)*$, and $1 \leq j \leq r_i$) and $F$ is a subset occurring in the matrices $m_i$

• $L(MAT)$ denotes the set of all languages that can be generated by matrix grammars -

• Theorem $L(MAT) = L(RE)$
• Theorem For each recursively enumerable language $L$, there is a matrix grammar $G$ in normal form such that $L (G) = L$.

While although this paper is about simple matrix grammars, it also states a definition of matrix grammars (not simple matrix grammars) that is a bit different with the above definition. It is stated that

• A matrix grammar (MG for short) is a pair $H = (G, M)$ where $G = (N,T,P,S)$ is a context-free grammar; $M$ is a finite language over the alphabet of rules $(M \subseteq P^*)$. For $x, y \in (N \cup T)^*, m \in M$, $x \Rightarrow y[m]$ in $H$, if and only if there are $x_0, x_1,\dots, x_n$ such that $x_0 = x, x_n = y$, and $x_0 \Rightarrow x_1[p_1] \Rightarrow x_2[p_2]) \Rightarrow \dots \Rightarrow x_n[p_n]$ in $G$, and $m = p_1 p_2 \dots p_n$, where $p_i \in P, 1 \leq i \leq n$, for some $n \geq 1$.

• Let $MT$ denotes the family of languages that is generated by matrix grammars

• $CF \subset MT \subset CS$

Question. How come when matrix grammars can generate recursively enumerable languages but it is still classified as a proper subset of the family of context-sensitive languages? Perhaps because they are different matrix grammars? I also read about it in this book but it is too complicated for me.

Additional Question. If a grammars $G$ can generate some context-sensitive languages (let's say that the family of languages generated as $XG$ ), is it still possible that the family of languages is going to be classified as a proper subset (strict inclusion) of $CS$, i.e. $XG \subset CS$?

Answer 1

Isn't the difference because matrix grammars exist with and without appearance checking? In the usual notation $\mathrm{MAT} \subset \mathrm{MAT}_\mathrm{ac} = \mathrm{RE}$.

A matrix grammar basically is a grammar with so-called matrices, lists of context-free type of productions $(A_1\to x_1, \dots, A_k\to x_k)$. There are two main variants of how to apply productions in matrix grammars. Either a matrix is applicable if all its productions can be applied in the given order. This is the less powerful variant, although we can generate $\{ a^nb^n c^n \mid n\ge 1\}$ that way.

Alternatively in a more powerful version some of the productions in a matrix may be marked as skipping productions. If the left-hand nonterminal in such production is present in the string it must be applied, when it is not present the production can be skipped. It is called appearance checking, and turns out to be a very powerful feature.

(added) In your new explicit definition of matrix grammars the set $F$ of occurrences of productions in the matrices are in fact the productions that can be skipped whenever the left side is not present (normally they would block the application of the matrix). So, when $F\neq\varnothing $ your model has appearance checking. Your first reference indeed has this feature, but does not mention it explicitly by name.