Regulated rewriting
   HOME

TheInfoList



OR:

Regulated rewriting is a specific area of
formal languages In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...
studying grammatical systems which are able to take some kind of control over the
production Production may refer to: Economics and business * Production (economics) * Production, the act of manufacturing goods * Production, in the outline of industrial organization, the act of making products (goods and services) * Production as a stati ...
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 = is a finite set of matrices, which are non-empty sequences m_ = _,...,p_/math>, with k(i)\geq 1, and 1 \leq i \leq n, where each p_ 1\leq j\leq k(i), is an ordered pair p_ = (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 = _\rightarrow R_,...,L_\rightarrow R_/math>
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) = \ is generated by the CFMG G =(N, T, M, S) where N = \ is the non-terminal set, T = \ is the terminal set, and the set of matrices is defined as M : \left \rightarrow abc\right/math>, \left \rightarrow aAbBcC\right/math>, \left \rightarrow aA,B\rightarrow bB,C\rightarrow cC\right/math>, \left \rightarrow a,B\rightarrow b,C\rightarrow c\right/math>.


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\rightarrow 2^ 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^ 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 = \ is the non-terminal set, T = \ is the terminal set, and the productions set is defined as P = \ 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) = \. 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) = \. Besides there are other grammars with regulated rewriting, the four cited above are good examples of how to extend
context-free grammars In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be empt ...
with some kind of control mechanism to obtain a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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'' {{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, Formal languages Formal methods