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:
“Then the justice,
In fair round belly with good capon lined,
With eyes severe and beard of formal cut,
Full of wise saws and modern instances;
And so he plays his part.”
—William Shakespeare (1564–1616)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)