[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$?