Regulated rewriting

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)\backslash geq\; 1$, and

$1\; \backslash leq\; i\; \backslash leq\; n$, where each

$p\_\{i\_\{j\}\}\; 1\backslash leq\; j\backslash leq\; k(i)$, is an ordered pair

$p\_\{i\_\{j\}\}\; =\; (L,\; R)$

being

$L\; \backslash in\; (N\; \backslash cup\; T)^*N(N\backslash cup\; T)^*,\; R\; \backslash in\; (N\backslash cup\; T)^*$

these pairs are called "productions", and are denoted

$L\backslash rightarrow\; R$. In these conditions the matrices can be written down as

$m\_i\; =\; [L\_\{i\_\{1\}\}\backslash rightarrow\; R\_\{i\_\{1\}\},...,L\_\{i\_\{k(i)\}\}\backslash 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 $\backslash lambda$-productions" if and only if the grammar $G=(N,\; T,\; P,\; S)$ has the corresponding property.

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

The context-sensitive language

$L(G)\; =\; \backslash \{\; a^nb^nc^n\; :\; n\backslash geq\; 1\backslash \}$

is generated by the $CFMG$

$G\; =(N,\; T,\; M,\; S)$ where

$N\; =\; \backslash \{S,\; A,\; B,\; C\backslash \}$ is the non-terminal set,

$T\; =\; \backslash \{a,\; b,\; c\backslash \}$ is the terminal set,

and the set of matrices is defined as

$M\; :$

$\backslash left[S\backslash rightarrow\; abc\backslash right]$,

$\backslash left[S\backslash rightarrow\; aAbBcC\backslash right]$,

$\backslash left[A\backslash rightarrow\; aA,B\backslash rightarrow\; bB,C\backslash rightarrow\; cC\backslash right]$,

$\backslash left[A\backslash rightarrow\; a,B\backslash rightarrow\; b,C\backslash rightarrow\; c\backslash right]$.

Basic concepts

Definition

A Time Variant Grammar is a pair $(G,\; v)$ where $G\; =\; (N,\; T,\; P,\; S)$

is a grammar and $v:\; \backslash mathbb\{N\}\backslash rightarrow\; 2^\{P\}$ is a function from the set of natural

numbers to the class of subsets of the set of productions.

Basic concepts

A Programmed Grammar is a pair $(G,\; s)$ where $G\; =\; (N,\; T,\; P,\; S)$

is a grammar and $s,\; f:\; P\backslash rightarrow\; 2^\{P\}$ are the success and fail functions from the set of productions

to the class of subsets of the set of productions.

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.

Consider the CFG

$G\; =\; (N,\; T,\; P,\; S)$ where

$N\; =\; \backslash \{S,\; A,\; B,\; C\backslash \}$ is the non-terminal set,

$T\; =\; \backslash \{a,\; b,\; c\backslash \}$ is the terminal set,

and the productions set is defined as

$P\; =\; \backslash \{p\_0,\; p\_1,\; p\_2,\; p\_3,\; p\_4,\; p\_5,\; p\_6\backslash \}$

being

$p\_0\; =\; S\backslash rightarrow\; ABC$

$p\_1\; =\; A\backslash rightarrow\; aA$,

$p\_2\; =\; B\backslash rightarrow\; bB$,

$p\_3\; =\; C\backslash rightarrow\; cC$

$p\_4\; =\; A\backslash rightarrow\; a$,

$p\_5\; =\; B\backslash rightarrow\; b$, and

$p\_6\; =\; C\backslash rightarrow\; c$.

Clearly,

$L(G)\; =\; \backslash \{\; a^*b^*c^*\backslash \}$.

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)\; =\; \backslash \{\; a^nb^nc^n\; :\; n\backslash geq\; 1\backslash \}$.

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.

• 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, [http://theo.cs.uni-magdeburg.de/dassow/tarraphd.pdf Grammars with Regulated Rewriting]. Lecture in the 5th PhD Program "Formal Languages and Applications", Tarragona, Spain, 2006.
• Abraham, S. 1965. [https://web.archive.org/web/20061209113626/http://acl.ldc.upenn.edu/C/C65/C65-1001.pdf Some questions of language theory], Proceedings of the 1965 International Conference On Computational Linguistics, pp. 1–11, Bonn, Germany,

Category:Formal languages

Category:Formal methods