Regulated rewriting explained

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={m1,m2,...,mn}

is a finite set of matrices, which are non-empty sequences

mi=

[p
i1
,...,p
ik(i)

]

, with

k(i)\geq1

, and

1\leqi\leqn

, where each
p
ij

1\leqj\leqk(i)

, is an ordered pair
p
ij

=(L,R)

being

L\in(N\cupT)*N(N\cupT)*,R\in(N\cupT)*

these pairs are called "productions", and are denoted

L → R

. In these conditions the matrices can be written down as

mi=

[L
i1

→

R
i1
,...,L
ik(i)

→

R
ik(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 namesThe context-sensitive language

L(G)=\{anbncn:n\geq1\}

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 → abc\right]

,

\left[S → aAbBcC\right]

,

\left[A → aA,B → bB,C → cC\right]

,

\left[A → a,B → b,C → 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:N → 2P

is a function from the set of naturalnumbers 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 productionsto 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(p1p2p

*(p
4p

5p6)

.

Combining the CFG grammar

G

and the regular expression

e

, we obtain the CFGWRCL

(G,e) =(G,p0(p1p2p

*(p
4p

5p6))

which generates the language

L(G)=\{anbncn:n\geq1\}

.

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

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Regulated rewriting".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2026, A B Cryer, All Rights Reserved. Cookie policy.