Regulated rewriting

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, [math]\displaystyle{ MG }[/math], is a four-tuple [math]\displaystyle{ G = (N, T, M, S) }[/math] where
1.- [math]\displaystyle{ N }[/math] is an alphabet of non-terminal symbols
2.- [math]\displaystyle{ T }[/math] is an alphabet of terminal symbols disjoint with [math]\displaystyle{ N }[/math]
3.- [math]\displaystyle{ M = {m_1, m_2,..., m_n} }[/math] is a finite set of matrices, which are non-empty sequences [math]\displaystyle{ m_{i} = [p_{i_1},...,p_{i_{k(i)}}] }[/math], with [math]\displaystyle{ k(i)\geq 1 }[/math], and [math]\displaystyle{ 1 \leq i \leq n }[/math], where each [math]\displaystyle{ p_{i_{j}} 1\leq j\leq k(i) }[/math], is an ordered pair [math]\displaystyle{ p_{i_{j}} = (L, R) }[/math] being [math]\displaystyle{ L \in (N \cup T)^*N(N\cup T)^*, R \in (N\cup T)^* }[/math] these pairs are called "productions", and are denoted [math]\displaystyle{ L\rightarrow R }[/math]. In these conditions the matrices can be written down as [math]\displaystyle{ m_i = [L_{i_{1}}\rightarrow R_{i_{1}},...,L_{i_{k(i)}}\rightarrow R_{i_{k(i)}}] }[/math]
4.- S is the start symbol

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

The classic example

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

The context-sensitive language [math]\displaystyle{ L(G) = \{ a^nb^nc^n : n\geq 1\} }[/math] is generated by the [math]\displaystyle{ CFMG }[/math] [math]\displaystyle{ G =(N, T, M, S) }[/math] where [math]\displaystyle{ N = \{S, A, B, C\} }[/math] is the non-terminal set, [math]\displaystyle{ T = \{a, b, c\} }[/math] is the terminal set, and the set of matrices is defined as [math]\displaystyle{ M : }[/math] [math]\displaystyle{ \left[S\rightarrow abc\right] }[/math], [math]\displaystyle{ \left[S\rightarrow aAbBcC\right] }[/math], [math]\displaystyle{ \left[A\rightarrow aA,B\rightarrow bB,C\rightarrow cC\right] }[/math], [math]\displaystyle{ \left[A\rightarrow a,B\rightarrow b,C\rightarrow c\right] }[/math].

Time Variant Grammars

Basic concepts
Definition
A Time Variant Grammar is a pair [math]\displaystyle{ (G, v) }[/math] where [math]\displaystyle{ G = (N, T, P, S) }[/math] is a grammar and [math]\displaystyle{ v: \mathbb{N}\rightarrow 2^{P} }[/math] is a function from the set of natural numbers to the class of subsets of the set of productions.

Programmed Grammars

Basic concepts

Definition

A Programmed Grammar is a pair [math]\displaystyle{ (G, s) }[/math] where [math]\displaystyle{ G = (N, T, P, S) }[/math] is a grammar and [math]\displaystyle{ s, f: P\rightarrow 2^{P} }[/math] 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, [math]\displaystyle{ GWRCL }[/math], is a pair [math]\displaystyle{ (G, e) }[/math] where [math]\displaystyle{ G = (N, T, P, S) }[/math] is a grammar and [math]\displaystyle{ e }[/math] is a regular expression over the alphabet of the set of productions.

A naive example

Consider the CFG [math]\displaystyle{ G = (N, T, P, S) }[/math] where [math]\displaystyle{ N = \{S, A, B, C\} }[/math] is the non-terminal set, [math]\displaystyle{ T = \{a, b, c\} }[/math] is the terminal set, and the productions set is defined as [math]\displaystyle{ P = \{p_0, p_1, p_2, p_3, p_4, p_5, p_6\} }[/math] being [math]\displaystyle{ p_0 = S\rightarrow ABC }[/math] [math]\displaystyle{ p_1 = A\rightarrow aA }[/math], [math]\displaystyle{ p_2 = B\rightarrow bB }[/math], [math]\displaystyle{ p_3 = C\rightarrow cC }[/math] [math]\displaystyle{ p_4 = A\rightarrow a }[/math], [math]\displaystyle{ p_5 = B\rightarrow b }[/math], and [math]\displaystyle{ p_6 = C\rightarrow c }[/math]. Clearly, [math]\displaystyle{ L(G) = \{ a^*b^*c^*\} }[/math]. Now, considering the productions set [math]\displaystyle{ P }[/math] as an alphabet (since it is a finite set), define the regular expression over [math]\displaystyle{ P }[/math]: [math]\displaystyle{ e=p_0(p_1p_2p_3)^*(p_4p_5p_6) }[/math].

Combining the CFG grammar [math]\displaystyle{ G }[/math] and the regular expression [math]\displaystyle{ e }[/math], we obtain the CFGWRCL [math]\displaystyle{ (G,e) =(G,p_0(p_1p_2p_3)^*(p_4p_5p_6)) }[/math] which generates the language [math]\displaystyle{ L(G) = \{ a^nb^nc^n : n\geq 1\} }[/math].

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 ISBN:3-540-61486-9 (set) (3540604200 : v. 1; 3540606483 : v. 2; 3540606491: v. 3)

• Dassow, Jürgen; Paun, G. 1990, Regulated Rewriting in Formal Language Theory ISBN:0387514147. 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,