# Generative power and classification of matrix grammars

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

• It looks like a mistake. – Yuval Filmus Oct 11 '15 at 7:07
• The statements are clearly contradictory. Either you read one or more sources wrong, or at least one of them is wrong. Can you quote the exact statements and name the sources? – Raphael Oct 11 '15 at 7:37
• Thank you, I have add the information needed as advised. – kate Oct 11 '15 at 18:28

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.
(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.
• Thank you! Your explanation about appearance checking is really easy to understand. I have an additional question if you don't mind: if a grammar can generate some context-sensitive languages, is it still possible that the grammar is going to be classified as a proper subset (strict inclusion) of $CS$? – kate Oct 11 '15 at 18:21