Regulated rewriting explained

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
A Matrix Grammar,

MG , is a four-tuple G = (N, T, M, S) where
1.- N is an alphabet of non-terminal symbols
2.- T is an alphabet of terminal symbols disjoint with N
3.- M = {m _{1,} m _{2,...,} m _{n}} is a finite set of matrices, which are non-empty sequences m _{i} = [p _{i _{1}} ,...,p _{i _{k(i)}} ] , with k(i)\geq 1 , and1 \leq i \leq n , where each p _{i _{j}} 1 \leq j\leq k(i) , is an ordered pairp _{i _{j}} = (L, R) beingL \in (N \cup T) ^{*N(N\cup} T) ^{*,} R \in (N\cup T) ^{*} these pairs are called "productions", and are denotedL → R . In these conditions the matrices can be written down asm _{i} = [L _{i _{1}} → R _{i _{1}} ,...,L _{i _{k(i)}} → R _{i _{k(i)}} ]
4.- S is the start symbol

Definition
Let

MG = (N, T, M, S) be a matrix grammar and let P the collection of all productions on matrices of MG .We said that MG is of type i according to Chomsky's hierarchy with i =0 , 1 , 2 , 3 , or "increasing length" or "linear" or "without λ -productions" if and only if the grammar G = (N, T, P, S) has the corresponding property.

The classic example

Note: taken from Abraham 1965, with change of nonterminals namesThe context-sensitive language

L(G) = \{ a ^{nb} ^{nc} ^{n} : n\geq 1 \} is generated by the CFMG G = (N, T, M, S) whereN = \{S, A, B, C\} is the non-terminal set, T = \{a, b, c\} is the terminal set,and the set of matrices is defined asM : \left[S → abc\right] ,\left[S → aAbBcC\right] ,\left[A → aA,B → bB,C → cC\right] ,\left[A → a,B → b,C → c\right] .

Time Variant Grammars

Basic concepts
Definition
A Time Variant Grammar is a pair

(G, v) where G = (N, T, P, S) is a grammar and v: N → 2 ^{P} is a function from the set of naturalnumbers to the class of subsets of the set of productions.

Programmed Grammars

Basic concepts

Definition

A Programmed Grammar is a pair

(G, s) where G = (N, T, P, S) is a grammar and s, f: P → 2 ^{P} are the success and fail functions from the set of productionsto the class of subsets of the set of productions.

Grammars with regular control language

Basic concepts

Definition
A Grammar With Regular Control Language,

GWRCL , is a pair (G, e) where G = (N, T, P, S) is a grammar and e is a regular expression over the alphabet of the set of productions.

A naive example

Consider the CFG

G = (N, T, P, S) whereN = \{S, A, B, C\} is the non-terminal set, T = \{a, b, c\} is the terminal set,and the productions set is defined asP = \{p _{0,} p _{1,} p _{2,} p _{3,} p _{4,} p _{5,} p _{6\}} being p _{0} = S → ABC p _{1} = A → aA ,p _{2} = B → bB ,p _{3} = C → cC p _{4} = A → a ,p _{5} = B → b , andp _{6} = C → c .Clearly,L(G) = \{ a ^{*b} ^{*c} ^{*\}} . Now, considering the productions set P as an alphabet (since it is a finite set),define the regular expression over P :e = p _{0(p} _{1p} _{2p} ^{*(p} ^{4 p} _{5p} _{6)} .

Combining the CFG grammar

G and the regular expressione , we obtain the CFGWRCL (G,e) = (G,p _{0(p} _{1p} _{2p} ^{*(p} ^{4 p} _{5p} _{6))} which generates the languageL(G) = \{ a ^{nb} ^{nc} ^{n} : n\geq 1 \} .

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, Grammars with Regulated Rewriting. Lecture in the 5th PhD Program "Formal Languages and Applications", Tarragona, Spain, 2006.
• Abraham, S. 1965. Some questions of language theory, Proceedings of the 1965 International Conference On Computational Linguistics, pp. 1–11, Bonn, Germany,