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:

## Contents

* 1 Matrix Grammars
* 1.1 Basic concepts
* 1.2 The classic example
* 2 Time Variant Grammars
* 3 Programmed Grammars
* 3.1 Definition
* 4 Grammars with regular control language
* 4.1 Basic concepts
* 4.2 A naive example
* 5 References

## 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=m1,m2,...,mn is a finite set of matrices, which are non-empty sequences mi=[pi1,...,pik(i)], with k(i)≥1, and 1≤i≤n, where each pij1≤j≤k(i), is an ordered pair pij=(L,R) being L∈(N∪T)*N(N∪T)*,R∈(N∪T)* these pairs are called "productions", and are denoted L->R. In these conditions the matrices can be written down as mi=[Li1->Ri1,...,Lik(i)->Rik(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 names

The context-sensitive language L(G)={anbncn:n≥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: [S->abc], [S->aAbBcC], [A->aA,B->bB,C->cC], [A->a,B->b,C->c].

## 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:ℕ->2P 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->2P 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={p0,p1,p2,p3,p4,p5,p6} being p0=S->ABC p1=A->aA, p2=B->bB, p3=C->cC p4=A->a, p5=B->b, and p6=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=p0(p1p2p3)*(p4p5p6).

Combining the CFG grammar G and the regular expression e, we obtain the CFGWRCL (G,e)=(G,p0(p1p2p3)*(p4p5p6)) which generates the language L(G)={anbncn:n≥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 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,

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Regulated rewriting. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Regulated_rewriting&oldid=254222"