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
Read more about this topic: Matrix Grammar
Famous quotes containing the words formal and/or definition:
“Two clergymen disputing whether ordination would be valid without the imposition of both hands, the more formal one said, “Do you think the Holy Dove could fly down with only one wing?””
—Horace Walpole (1717–1797)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)