Matrix Grammar

Matrix grammar is a formal grammar in which the production rules are grouped into finite sequences. The production rules cannot be applied individually, only as a sequence. When such a sequence is applied, the replacement is carried out according to each rule in the sequence, from the first to the last. The sequences are called matrices. A matrix grammar is an extension of a context-free grammar.

Formal definition

A matrix grammar is an ordered quadruple

where

• is a finite set of nonterminal symbols
• is a finite set of terminal symbols
• is the start symbol
• is a finite set of nonempty sequences of ordered pairs

The pairs are called production rules and are written as . The sequences are called matrices and are written as

Let be the set of all production rules in the matrices of the matrix grammar . Then the grammar is a grammar of type , non-contracting, linear, -free, context-free or context-sensitive if and only if the grammar has this property.

For a matrix grammar a binary relation is defined, also denoted . For any , holds if and only if there exists an integer such that there exist words

over the set V and

• and
• 
• and

If these conditions are satisfied, it is also said that holds with the specification .

Let be the reflexive transitive closure of the relation . Then the language generated by the matrix grammar is defined as follows:

Example

Consider the matrix grammar

where is the collection of the following matrices:

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

See also

• [[b8374]]

See also

• Formal Languages and Formal Grammars