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, M G {\displaystyle MG} , is a four-tuple G = ( N , T , M , S ) {\displaystyle G=(N,T,M,S)} where 1.- N {\displaystyle N} is an alphabet of non-terminal symbols 2.- T {\displaystyle T} is an alphabet of terminal symbols disjoint with N {\displaystyle N}
3.- M = m 1 , m 2 , . . . , m n {\displaystyle 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 ) ] {\displaystyle m_{i}=[p_{i_{1}},...,p_{i_{k(i)}}]} , with k ( i ) ≥ 1 {\displaystyle k(i)\geq 1} , and
1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} , where each
p i j 1 ≤ j ≤ k ( i ) {\displaystyle p_{i_{j}}1\leq j\leq k(i)} , is an ordered pair
p i j = ( L , R ) {\displaystyle p_{i_{j}}=(L,R)}
being
L ∈ ( N ∪ T ) ∗ N ( N ∪ T ) ∗ , R ∈ ( N ∪ T ) ∗ {\displaystyle L\in (N\cup T)^{*}N(N\cup T)^{*},R\in (N\cup T)^{*}}
these pairs are called "productions", and are denoted
L → R {\displaystyle L\rightarrow R} . In these conditions the matrices can be written down as
m i = [ L i 1 → R i 1 , . . . , L i k ( i ) → R i k ( i ) ] {\displaystyle 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 M G = ( N , T , M , S ) {\displaystyle MG=(N,T,M,S)} be a matrix grammar and let P {\displaystyle P}
the collection of all productions on matrices of M G {\displaystyle MG} . We said that M G {\displaystyle MG} is of type i {\displaystyle i} according to Chomsky's hierarchy with i = 0 , 1 , 2 , 3 {\displaystyle i=0,1,2,3} , or "increasing length" or "linear" or "without λ {\displaystyle \lambda } -productions" if and only if the grammar G = ( N , T , P , S ) {\displaystyle 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 n b n c n : n ≥ 1 } {\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 1\}}
is generated by the C F M G {\displaystyle CFMG}
G = ( N , T , M , S ) {\displaystyle G=(N,T,M,S)} where
… excerpt ends here. Continue reading the full article.
