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)
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)