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:
“Good gentlemen, look fresh and merrily.
Let not our looks put on our purposes,
But bear it as our Roman actors do,
With untired spirits and formal constancy.”
—William Shakespeare (1564–1616)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)