5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It looks like a mistake. $\endgroup$ – Yuval Filmus Oct 11 '15 at 7:07
  • 2
    $\begingroup$ 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? $\endgroup$ – Raphael Oct 11 '15 at 7:37
  • $\begingroup$ Thank you, I have add the information needed as advised. $\endgroup$ – kate Oct 11 '15 at 18:28
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – kate Oct 11 '15 at 18:21
  • $\begingroup$ Of course, it might be the case that the grammars generate some, but not all of the CS languages. (Without further research I do not have a good feeling of how complicated the counter example is, the example of a language not in CS.) $\endgroup$ – Hendrik Jan Oct 11 '15 at 18:59
  • $\begingroup$ Thank you very much for your fast and easy-to-understand clarification. I don't know how complicated it is. So I have to test all examples of CS then? Or perhaps if I can show that if it can generate (some) RE languages then problem solved? I'm also interested in the examples of languages not in CS (i.e. in RE). Or perhaps better trying to learn characterization of RE such as using homomorphism? Sorry for the questions bombarding. Just curious and hope to get the idea how to do it. $\endgroup$ – kate Oct 11 '15 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.