Regulated rewriting is a specific area of formal languages studying grammatical systems which are able to take some kind of control over the production applied in a derivation step. For this reason, the grammatical systems studied in Regulated Rewriting theory are also called "Grammars with Controlled Derivations". Among such grammars can be noticed:
Definition<br> A Matrix Grammar, , is a four-tuple where<br /> 1.- is an alphabet of non-terminal symbols<br /> 2.- is an alphabet of terminal symbols disjoint with <br /> 3.- is a finite set of matrices, which are non-empty sequences , with , and , where each , is an ordered pair
being
these pairs are called "productions", and are denoted . In these conditions the matrices can be written down as <br /> 4.- S is the start symbol
Definition<br> Let be a matrix grammar and let the collection of all productions on matrices of . We said that is of type according to Chomsky's hierarchy with , or "increasing length" or "linear" or "without -productions" if and only if the grammar has the corresponding property.
The context-sensitive language
is generated by the where is the non-terminal set, is the terminal set, and the set of matrices is defined as
, , , .
Basic concepts <br /> Definition<br /> A Time Variant Grammar is a pair where is a grammar and is a function from the set of natural numbers to the class of subsets of the set of productions.
Basic concepts
A Programmed Grammar is a pair where is a grammar and are the success and fail functions from the set of productions to the class of subsets of the set of productions.
Definition<br> A Grammar With Regular Control Language, , is a pair where is a grammar and is a regular expression over the alphabet of the set of productions.
Consider the CFG where is the non-terminal set, is the terminal set, and the productions set is defined as
being
, ,
, , and . Clearly, . Now, considering the productions set as an alphabet (since it is a finite set), define the regular expression over : .
Combining the CFG grammar and the regular expression , we obtain the CFGWRCL
which generates the language .
Besides there are other grammars with regulated rewriting, the four cited above are good examples of how to extend context-free grammars with some kind of control mechanism to obtain a Turing machine powerful grammatical device.