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, $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$ , and $1 \leq i \leq n$ , where each $p_{i_{j}} 1\leq j\leq k(i)$ , is an ordered pair $p_{i_{j}} = (L, R)$ being $L \in (N \cup T)^*N(N\cup T)^*, R \in (N\cup T)^*$ these pairs are called "productions", and are denoted $L\rightarrow R$ . In these conditions the matrices can be written down as $m_i = [L_{i_{1}}\rightarrow R_{i_{1}},...,L_{i_{k(i)}}\rightarrow 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 $\lambda$ -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 names

The context-sensitive language $L(G) = \{ a^nb^nc^n : n\geq 1\}$ is generated by the $CFMG$ $G =(N, T, M, S)$ where $N = \{S, A, B, C\}$ is the non-terminal set, $T = \{a, b, c\}$ is the terminal set, and the set of matrices is defined as $M :$ $\left[S\rightarrow abc\right]$ , $\left[S\rightarrow aAbBcC\right]$ , $\left[A\rightarrow aA,B\rightarrow bB,C\rightarrow cC\right]$ , $\left[A\rightarrow a,B\rightarrow b,C\rightarrow 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: \mathbb{N}\rightarrow 2^{P}$ 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 $(G, s)$ where $G = (N, T, P, S)$ is a grammar and $s, f: P\rightarrow 2^{P}$ 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, $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)$ where $N = \{S, A, B, C\}$ is the non-terminal set, $T = \{a, b, c\}$ is the terminal set, and the productions set is defined as $P = \{p_0, p_1, p_2, p_3, p_4, p_5, p_6\}$ being $p_0 = S\rightarrow ABC$ $p_1 = A\rightarrow aA$ , $p_2 = B\rightarrow bB$ , $p_3 = C\rightarrow cC$ $p_4 = A\rightarrow a$ , $p_5 = B\rightarrow b$ , and $p_6 = C\rightarrow 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_3)^*(p_4p_5p_6)$ .

Combining the CFG grammar $G$ and the regular expression $e$ , we obtain the CFGWRCL $(G,e) =(G,p_0(p_1p_2p_3)^*(p_4p_5p_6))$ which generates the language $L(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.

Sources

[1] Salomaa, Arto (1973) Formal languages Academic Press, ACM monograph series

[2] 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)

[3] Dassow, Jurgen; Paun, G. 1990 Regulated Rewriting in Formal Language Theory ISBN 0387514147. Springer-Verlag New York, Inc. Secaucus, NJ, USA Pages: 308. Medium: Hardcover.

[4] Dassow, Jurgen; von-Guericke, Otto Grammars with Regulated Rewriting Available at: and ()

[5] Abraham, S. 1965. "Some questions of language theory", Proceedings of the 1965 International Conference On Computational Linguistics, pp 1 – 11, Bonn, Germany Available at:

This article is issued from Wikipedia - version of the Saturday, October 04, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.