Matrix grammar

Last updated July 07, 2021

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.

Formal definition

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

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

$\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 $P\to Q$ . The sequences are called matrices and can be written as

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

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

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

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

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

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

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

Examples

Consider the matrix grammar

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

where $M$ is a collection containing the following matrices:

$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

$L=\{a^{n}b^{n}c^{n}|n\geq 1\}.$ The associate word of $a^{n}b^{n}c^{n}$ is $Aw(a^{n}b^{n}c^{n})=m_{0}m_{1}^{n-2}m_{2},\forall n\geq 2$ and $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

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

where $M$ is a collection containing the following matrices:

$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

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

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

Properties

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

Trivially, $MAT$ is included in ${\ce {MAT^{\lambda }}}$ .
All context-free languages are in $MAT$ , and all languages in ${\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 ${\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 ${\ce {MAT^{\lambda }}}$ which are not in $MAT$ , and it is neither known whether ${\ce {MAT^{\lambda }}}$ contains languages which are not context-sensitive .

Related Research Articles

In physics, the Lorentz transformations are a six-parameter family of linear transformations from a coordinate frame in spacetime to another frame that moves at a constant velocity relative to the former. The respective inverse transformation is then parameterized by the negative of this velocity. The transformations are named after the Dutch physicist Hendrik Lorentz.

In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,

In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints. It is named after the mathematician Joseph-Louis Lagrange. The basic idea is to convert a constrained problem into a form such that the derivative test of an unconstrained problem can still be applied. The relationship between the gradient of the function and gradients of the constraints rather naturally leads to a reformulation of the original problem, known as the Lagrangian function.

In linear algebra, the Cayley–Hamilton theorem states that every square matrix over a commutative ring satisfies its own characteristic equation.

In mathematics, particularly in linear algebra, a skew-symmetricmatrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition

In mathematics, an Hermitian matrix is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the $i$ -th row and $j$ -th column is equal to the complex conjugate of the element in the $j$ -th row and $i$ -th column, for all indices $i$ and $j$ :

In linear algebra, a square matrix $is called diagonalizable or non-defective if it is similar to a diagonal matrix, i.e., if there exists an invertible matrix and a diagonal matrix such that, or equivalently . For a finite-dimensional vector space, a linear map is called diagonalizable if there exists an ordered basis of consisting of eigenvectors of . These definitions are equivalent: if has a matrix representation as above, then the column vectors of form a basis consisting of eigenvectors of, and the diagonal entries of are the corresponding eigenvalues of; with respect to this eigenvector basis, is represented by . Diagonalization is the process of finding the above and .$

In mathematics, the Rayleigh quotient for a given complex Hermitian matrix M and nonzero vector x is defined as:

In numerical analysis, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix. These eigenvalue algorithms may also find eigenvectors.

In mathematics, in particular functional analysis, the singular values, or s-numbers of a compact operator T : X → Y acting between Hilbert spaces X and Y, are the square roots of non-negative eigenvalues of the self-adjoint operator T^*T.

In geometry, a barycentric coordinate system is a coordinate system in which the location of a point is specified by reference to a simplex. The barycentric coordinates of a point can be interpreted as masses placed at the vertices of the simplex, such that the point is the center of mass of these masses. These masses can be zero or negative; they are all positive if and only if the point is inside the simplex.

In mathematics, the polar decomposition of a square real or complex matrix $is a factorization of the form, where is a unitary matrix and is a positive-semidefinite Hermitian matrix, both square and of the same size.$

In probability theory and mathematical physics, a random matrix is a matrix-valued random variable—that is, a matrix in which some or all elements are random variables. Many important properties of physical systems can be represented mathematically as matrix problems. For example, the thermal conductivity of a lattice can be computed from the dynamical matrix of the particle-particle interactions within the lattice.

In mathematics, a symmetric bilinear form on a vector space is a bilinear map from two copies of the vector space to the field of scalars such that the order of the two vectors does not affect the value of the map. In other words, it is a bilinear function $that maps every pair of elements of the vector space to the underlying field such that for every and in . They are also referred to more briefly as just symmetric forms when "bilinear" is understood.$

In linear algebra, an eigenvector or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted by $, is the factor by which the eigenvector is scaled.$

In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of a indefinite nonsymmetric system of linear equations. The method approximates the solution by the vector in a Krylov subspace with minimal residual. The Arnoldi iteration is used to find this vector.

In linear algebra, eigendecomposition or sometimes spectral decomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way.

In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices $A$ with non-negative integer entries and pairs $(P, Q)$ of semistandard Young tableaux of equal shape, whose size equals the sum of the entries of $A$ . More precisely the weight of $P$ is given by the column sums of $A$ , and the weight of $Q$ by its row sums. It is a generalization of the Robinson–Schensted correspondence, in the sense that taking $A$ to be a permutation matrix, the pair $(P, Q)$ will be the pair of standard tableaux associated to the permutation under the Robinson–Schensted correspondence.

In mathematics, particularly linear algebra, the Schur–Horn theorem, named after Issai Schur and Alfred Horn, characterizes the diagonal of a Hermitian matrix with given eigenvalues. It has inspired investigations and substantial generalizations in the setting of symplectic geometry. A few important generalizations are Kostant's convexity theorem, Atiyah–Guillemin–Sternberg convexity theorem, Kirwan convexity theorem.

In mathematics, in linear algebra, a Weyr canonical form is a square matrix satisfying certain conditions. A square matrix is said to be in the Weyr canonical form if the matrix satisfies the conditions defining the Weyr canonical form. The Weyr form was discovered by the Czech mathematician Eduard Weyr in 1885. The Weyr form did not become popular among mathematicians and it was overshadowed by the closely related, but distinct, canonical form known by the name Jordan canonical form. The Weyr form has been rediscovered several times since Weyr’s original discovery in 1885. This form has been variously called as modified Jordan form,reordered Jordan form,second Jordan form, and H-form. The current terminology is credited to Shapiro who introduced it in a paper published in the American Mathematical Monthly in 1999.

References

↑ 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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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 .

[1]