Misplaced Pages

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (April 2024) (Learn how and when to remove this message)

A matrix grammar is a formal grammar in which instead of single productions, productions are grouped together into finite sequences. A production cannot be applied separately, it must be applied in sequence. In the application of such a sequence of productions, the rewriting is done in accordance to each production in sequence, the first one, second one etc. till the last production has been used for rewriting. The sequences are referred to as matrices.

Matrix grammar is an extension of context-free grammar, and one instance of a controlled grammar.

Formal definition

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}.}$

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

${\displaystyle m=.}$

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 }$ 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\}.}$

Examples

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}:,\quad m_{1}:,\quad m_{2}:}$

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}:,\quad m_{1}:,\quad m_{2}:,\quad m_{3}:}$

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}}$.

Properties

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.

Open problems

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 .

References

1. Salomaa, Arto (March 1972). "Matrix grammars with a leftmost restriction" (PDF). Information and Control. 20 (2): 143–149. doi:10.1016/S0019-9958(72)90332-4.

Footnotes

• Á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

• Formal languages