Matrix grammar

A matrix grammar is an ordered quadruple ${\displaystyle G=(V_{N},V_{T},X_{0},M)}$ where

• ${\displaystyle V_{N}}$ is a finite set of non-terminals
• ${\displaystyle V_{T}}$ is a finite set of terminals
• ${\displaystyle X_{0}}$ is a special element of ${\displaystyle V_{N}}$, viz. the starting symbol
• ${\displaystyle M}$ is a finite set of non-empty sequences whose elements are ordered pairs ${\displaystyle (P,Q)}$ where

${\displaystyle \quad P\in V^{*}V_{N}V^{*},\quad Q\in V^{*},\quad V=V_{N}\cup V_{T}.}$[1]

The pairs are called productions, written as ${\displaystyle P\to Q}$. The sequences are called matrices and can be written as

${\displaystyle m=[P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}].}$

Let ${\displaystyle F}$ be the set of all productions appearing in the matrices ${\displaystyle m}$ of a matrix grammar ${\displaystyle G}$. Then the matrix grammar ${\displaystyle G}$ is of type-${\displaystyle i,i=0,1,2,3}$, length-increasing, linear, ${\displaystyle \lambda }$-free, context-free or context-sensitive if and only if the grammar ${\displaystyle G_{1}=(V_{N},V_{T},X_{0},F)}$ has the following property.

For a matrix grammar ${\displaystyle G}$, a binary relation ${\displaystyle \Rightarrow _{G}}$ is defined; also represented as ${\displaystyle \Rightarrow }$. For any ${\displaystyle P,Q\in V^{*}}$, ${\displaystyle P\Rightarrow Q}$ holds if and only if there exists an integer ${\displaystyle r\geq 1}$ such that the words

${\displaystyle \alpha _{1},,\ldots ,\alpha _{r+1},\quad P_{1},\ldots ,P_{r},\quad Q_{1},\ldots ,Q_{r},\quad R_{1},\ldots ,R_{r},\quad ,R^{1},\ldots ,R^{r}}$

over V exist and

• ${\displaystyle \alpha _{1}=P}$ and ${\displaystyle \alpha _{r+1}=Q}$
• ${\displaystyle [P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}]}$ is one of the matrices of ${\displaystyle G}$
• ${\displaystyle \alpha _{i}=R_{i}P_{i}R^{i}}$ and ${\displaystyle \alpha _{i+1}=R_{i}Q_{i}R^{i}}$ for all ${\displaystyle i}$ such that ${\displaystyle 1\leq i\leq r.}$

Let ${\displaystyle \Rightarrow ^{*}}$ be the reflexive transitive closure of the relation ${\displaystyle \Rightarrow }$. Then, the language generated by the matrix grammar ${\displaystyle G}$ is given by

${\displaystyle L(G)=\{P\in {V_{T}}^{*}|X_{0}\Rightarrow ^{*}P\}.}$

Consider the matrix grammar

${\displaystyle G=(\{S,X,Y\},\{a,b,c\},S,M)}$

where ${\displaystyle M}$ is a collection containing the following matrices:

${\displaystyle m_{0}:[S\rightarrow XY],\quad m_{1}:[X\rightarrow aXb,Y\rightarrow cY],\quad m_{2}:[X\rightarrow ab,Y\rightarrow c]}$

These matrices, which contain only context-free rules, generate the context-sensitive language

${\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}.}$ The associate word of ${\displaystyle a^{n}b^{n}c^{n}}$ is ${\displaystyle Aw(a^{n}b^{n}c^{n})=m_{0}m_{1}^{n-2}m_{2},\forall n\geq 2}$ and ${\displaystyle Aw(abc)=m_{0}m_{2}}$.

This example can be found on pages 8 and 9 of in the following form: Consider the matrix grammar

${\displaystyle G=(\{S,X,Y,Z\},\{a,b,c\},S,M)}$

where ${\displaystyle M}$ is a collection containing the following matrices:

${\displaystyle m_{0}:[S\rightarrow abc],\quad m_{1}:[S\rightarrow aXbYcZ],\quad m_{2}:[X\rightarrow aX,Y\rightarrow bY,Z\rightarrow cZ],\quad m_{3}:[X\rightarrow ab,Y\rightarrow b,Z\rightarrow c]}$

These matrices, which contain only context-regular rules, generate the context-sensitive language

${\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}.}$

The associate word of ${\displaystyle a^{n}b^{n}c^{n}}$ is ${\displaystyle Aw(a^{n}b^{n}c^{n})=m_{1}m_{2}^{n-2}m_{3},\forall n\geq 2}$ and ${\displaystyle Aw(abc)=m_{0}}$.

Let ${\displaystyle {\ce {MAT^{\lambda }}}}$ be the class of languages produced by matrix grammars, and MAT the class of languages produced by ${\displaystyle \lambda }$-free matrix grammars.

• Trivially, MAT is included in ${\displaystyle {\ce {MAT^{\lambda }}}}$.
• All context-free languages are in MAT, and all languages in ${\displaystyle {\ce {MAT^{\lambda }}}}$ are recursively enumerable.
• MAT is closed under union, concatenation, intersection with regular languages and permutation.
• All languages in MAT can be produced by a context-sensitive grammar.
• There exists a context-sensitive language which does not belong to ${\displaystyle {\ce {MAT^{\lambda }}}}$ .
• Each language produced by a matrix grammar with only one terminal symbol is regular.

It is not known whether there exist languages in ${\displaystyle {\ce {MAT^{\lambda }}}}$ which are not in MAT, and it is neither known whether ${\displaystyle {\ce {MAT^{\lambda }}}}$ contains languages which are not context-sensitive .

• ^ Ábrahám, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1–11.
• ^ Gheorghe Păun, Membrane Computing: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. pp 30–32