“Matrix grammar”的意思、由来-开放百科全书

词条

Matrix grammar

释义

Formal definition
Examples
Properties
Open problems
References
Footnotes

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

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

Examples

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

The associate word of

and

This example can be found on pages 8 and 9 of {{ref|Abraham1965}} in the following form:

Consider the matrix grammar

where is a collection containing the following matrices:

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

The associate word of

and

Properties

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

Trivially, {{math|MAT}} is included in MAT^\\lambda.
All context-free languages are in {{math|MAT}}, and all languages in MAT^\\lambda are recursively enumerable.
{{math|MAT}} is closed under union, concatenation, intersection with regular languages and permutation.
All languages in {{math|MAT}} can be produced by a context-sensitive grammar.
There exists a context-sensitive language which does not belong to MAT^\\lambda {{ref|Paun}}.
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 MAT^\\lambda which are not in {{math|MAT}}, and it is neither known whether MAT^\\lambda contains languages which are not context-sensitive {{ref|Paun}}.

References

Footnotes

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

1 : Formal languages

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。