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:

Matrix Grammars

Basic concepts

Definition where is an alphabet of non-terminal symbols 4.- S is the start symbol

Definition-productions" if and only if has the corresponding property.

The classic example

1. Note: taken from Abraham 1965, with change of nonterminals names

.

Time Variant Grammars

Basic concepts Definition is a function from the set of natural numbers to the class of subsets of the set of productions.

Programmed Grammars

Basic concepts

Definition

are the success and fail functions from the set of productions to the class of subsets of the set of productions.

Grammars with regular control language

Basic concepts

Definition A Grammar With Regular Control Language is a regular expression over the alphabet of the set of productions.

A naive example

.

.

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.

References

• Salomaa, Arto (1973) Formal languages. Academic Press, ACM monograph series

• Rozenberg, G.; Salomaa, A. (eds.) 1997, Handbook of formal languages. Berlin; New York : Springer (set) (3540604200 : v. 1; 3540606483 : v. 2; 3540606491: v. 3)

• Dassow, Jürgen; Paun, G. 1990, Regulated Rewriting in Formal Language Theory . Springer-Verlag New York, Inc. Secaucus, New Jersey, USA, Pages: 308. Medium: Hardcover.

• Dassow, Jürgen, . Lecture in the 5th PhD Program "Formal Languages and Applications", Tarragona, Spain, 2006.

• Abraham, S. 1965. , Proceedings of the 1965 International Conference On Computational Linguistics, pp.1–11, Bonn, Germany,