Matrix grammar
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 the 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
where
-
is a finite set of non-terminals
-
is a finite set of terminals
-
is a special element of
, viz. the starting symbol
-
is a finite set of non-empty sequences whose elements are ordered pairs
The pairs are called productions, written as . The sequences are called matrices and can be written as
Let be the set of all productions appearing in the matrices
of a matrix grammar
. Then the matrix grammar
is of type-
, length-increasing, linear,
-free, context-free or context-sensitive if and only if the grammar
has the following property.
For a matrix grammar , a binary relation
is defined; also represented as
. For any
,
holds if and only if there exists an integer
such that the words
over V exist and
-
and
-
is one of the matrices of
-
and
If the above conditions are satisfied, it is also said that holds with
as the specifications.
Let be the reflexive transitive closure of the relation
. Then, the language generated by the matrix grammar
is given by
Example
Consider the matrix grammar
where is a collection containing the following matrices:
These matrices, which contain only context-free rules generate the context-sensitive language
This example can be found on pages 8 and 9 of .
Properties
Let be the class of languages produced by matrix grammars, and
the class of languages produced by
-free matrix grammars.
- Trivially,
is included in
.
- All context-free languages are in
, and all languages in
are recursively enumerable.
-
is closed under union, concatenation, intersection with regular languages and permutation.
- All languages in
can be produced by a context-sensitive grammar.
- There exists some languages in
which can not be produced by a context-sensitive grammar.
- 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 which are not in
, and it is neither known whether
contains languages which are not context-sensitive .