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 A Matrix Grammar,
is an alphabet of non-terminal symbols 2.-
is an alphabet of terminal symbols disjoint with
is a finite set of matrices, which are non-empty sequences
these pairs are called "productions", and are denoted
In these conditions the matrices can be written down as
4.- S is the start symbol Definition Let
be a matrix grammar and let
the collection of all productions on matrices of
according to Chomsky's hierarchy with
, or "increasing length" or "linear" or "without
The context-sensitive language
is the non-terminal set,
is the terminal set, and the set of matrices is defined as
{\displaystyle \left[A\rightarrow aA,B\rightarrow bB,C\rightarrow cC\right]}
Basic concepts Definition A Time Variant Grammar is a pair
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
are the success and fail functions from the set of productions to the class of subsets of the set of productions.
Definition A Grammar With Regular Control Language,
is a regular expression over the alphabet of the set of productions.
is the non-terminal set,
is the terminal set, and the productions set is defined as
Now, considering the productions set
as an alphabet (since it is a finite set), define the regular expression over
Combining the CFG grammar
, we obtain the CFGWRCL
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.