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:
“True variety is in that plenitude of real and unexpected elements, in the branch charged with blue flowers thrusting itself, against all expectations, from the springtime hedge which seems already too full, while the purely formal imitation of variety ... is but void and uniformity, that is, that which is most opposed to variety....”
—Marcel Proust (1871–1922)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)