This paper presentsnew models for generating matrix languages. These models are based on multigenerative grammar systems that simultaneouslygenerateseveral strings in a parallel way. The componentsof these models are context-free grarrrmars,working in a general way. The rewritten nonterminalsaredeterminedby a finite setof nonterminalsequences.
The formal language theory has intensively investigatedvarious grammar systems (see [1], l2l, [8]), which consist of several cooperating components,usually representedby grammars.Although this variety is extremelybroad, all thesegrammar systemsalways use a derivation that generatesa single string. In this paper,however, we introducegrammarsystemsthat simultaneouslygenerateseveralstrings,which are subsequentlycomposedin a single string by some common string operation,such as concatenation.
More precisely, for a positive integer n, an r-multigenerative grammar systemdiscussedin this paper works with n context-freegrarnmaticalcomponentsin a general way-{hat is, in every derivation step, each of these componentsrewrites any nonterminal occurring in its current sentential form. These n derivations are controled n-tuples of nonterminals or rules. Under a control like this, the grammar system generatesn strings, out of which the strings that belong to the generated languageare made by some basic operations.Specifically, these operationsinclude union, concatenationand a selectionof the string generatedby the first component.
In this paper, we prove that all the multigenerative grammar systemsunder discussion characterize the family of languages, which is generated by matrix grammars.Besidesthis fundamentalresult, we give severaltransformationalgorithms of thesemultigenerativegrammarsystems.
This paper assumesthat the readeris familiar with the formal languagetheory (see [4]). For a set, Q, carcl(Q) denotes the cardinality of Q. For an alphabet, V, f representsthe free monoid generatedby V under the operationof concatenation.The unit of I is denoted by e. Set I/ : I - {e}; algebraically, X rs thus the free semigroupgeneratedby Zunder the operationof concatenation.
A context-freegrammar is a quadruple,G: (N, T, P, 8, whereN and T arc disjoint alphabets. Symbols in N and T arc referred to as nonterminals and terminals, respectively,and S e N is the start symbol of G. P is a finite setof rules of the form A ) x, where A e l,'l and x c (N wT).. To declarethat a label r denotesthe rule, we write as r: A-+ x.Letu, v e (Nu 7)'. For everyr: A -> x e P, write uAv = uxv lr], or simply uAv > uxv. Let =' denote the transitive-reflexive closure of =. The languageof G, L(G),is definedasL(G) : {w:S -* w rn G,for some, e t' 7.
A matrix grammar is a pair, H : (G, A4),where G : (N, T, P, S) is a context-free g r a m m aar n d M i s a f i n i t e l a n g u a g e o v e r a l p h a b e t P , M c . PL' e. t x 6 ,x t , . . . , x n e ( l ' , 1 u T)- for any n ) 0, xi-1) xi lpil in G for all i: l, ..., n andppz...pn e M. Then matrix grammarH makesdirect derivation stepfrom xsto xr, denotedzISxs :> xn.Let =. denotethe transitive-reflexiveclosureof =. The languageof H, L(H), is defined asL(11): {w: S 3* w in H, for some* e t'y.
Dejinition 1. An n-multigenerative nonterminal-synchronizedgrammar system (nMGN) is an n+l tuple,
f : ( G r ,G z ,. . . , G n ,Q ) , where Gi: (Ni, Ti,Pi, S,) is a context-freegrammarfor eachi: l, ...,,n, andQ rs a finite set of n-tuplesof the form (At, Ar, ..., An),whereAi e Ni for all i: t, ..., n. Then, a sententialn-form of n-MGN is an z-tuple of the form X: (xv xz, ..., xn), wherexi e (Niv-1T)' for all i : I, ...) n.Let y: (urAp1,u2A2y2..,., u,Anv) and7 : (uppy u2x2r2.,.., u,&rrr) be two sententialn-fotm, whereAi e Ni, Lti,vi, x; e (//, t-r Z;).for all i : 1, ..., n. LetAi -+ xi € Pifor all i : I, ..., n and(At, A2, ..., Ar) e Q. Then X directly derives X in f, denotedby X = X. h the standardway, we generalize= to -k, k ) 0, 3*, and=*. Then-languageof f , n-L(f), is definedas n - L ( f ) : { ( w r w, 2 , . . . , w , ) : ( S , , S r , . . . , S , , ) = *w( rz,,,. . . , w , ) , w , Te 1f*o r a l li : 7 , . . . , n } . The languagegeneratedbyl in the unionmode,Lu,io,(l), is definedas
L u n i o n ( l ) :{ w : ( w r ,w r , . . . , w n )e n - L ( l ) , w e { w i :i : l , . . . ,n ) } .
The languagegeneratedby I in the concatenationmode,L"on,(f), is definedas
Lronr(l): {wtwz...wn: (w5 w2, ..., wn) e n-L(l)}.
The languogegeneratedby I in thefirst mode,Lnn,(l), is defined as
Lp,r,(l): {wi (wr,wr, ..., wr) e n-L(l)|.
Example1. f : (Gr, Gz,Q), whereGr : ({Sr,I ,), {a, b, c}, {Sr -+ aS1,S1-->aA6 A1 -->bA(, At -->bc\, Sr),Gz: ({Sz,Ar.}, {d}, {Sz-+ SzAzS,z-) Az,Az -+ d), Sz),Q: {(S', Sz),(Av Az)\ is a 2-multigenerativenonterminal-synchronizedgrammar system. W e h a v e2 - L ( f ) : { ( a n b n c ' , d n ) , n >l } , L u , i o n ( f ): { a ' b n c ' : n } l } u { d ' : n > 1 } , Lrorr(l): {anbnc'd'n: ) | }, andLn^,(f): {anb'c':n> l}.
DeJinition 2. An n-multigenerativerule-synchronizedgrammar system (n-MGR) is n+l tuple
f : ( G t , G z ,. . . , G * Q ) , where Gi: (Ni, Ti, Pi, S,) is a context-freegrammarfor eachi: l, ..., fl, and Q is a finitesetof n-tuplesof the form (pt,pr, ...,pn),wherepi e Pt for all i: l, ...,fl.A sententialn-form for n-MGR is defined as the sententialn-form for an n-MGN. Let y : (utA1r1u,2A2r2.,.., u,y'4r)t and X : (utxp1,u2x2v2..,., u,{nvr)aretwo sententianl form, whereAi € Ni,Lti,ri,xi e (,Mu, Ti)-for all i: 1, ...) n. Letpi: Ai -+ xi € Pi for all i : I, ..., n and(pv pr,, ..., pn) e Q. Then X directly derives 1 in f, denotedby X = X. An n-Ianguagefor any n-MGR is defined as the n-Ianguagefor any n-MGN, and a languagegeneratedby n-MGN in the X mode, for eachX e {union, conc,first}, is def,rnedasthe languagegeneratedby n-MGR in theX mode.
Example2. f : (Gt, Gz,Q),whereGr : ({St, Ar}, {a, b, c}, {1: 51 -) rzS12,: 51-+
aA1,3:Ar -) bAp,4z A1 -->bc\, Sr),Gz: ({Sz}, {d}, {l: ,S 2-) S2S2,2Szz-+,S23,: 52
-+ d|, Sz),Q : {(1, l), (
t 0 : {Qqr-) /r, Az -+ x2, '.., An ) xr):Ai ) xi e P; for all i : 1, ..., n, and ( A v A z , . . . , A ne) Q ) . o . o
Input' n-MGR f : (G', Gz,..., Gn,Q) O u t p z t . n. - M G N f : 1G , , G r , . . . , G , , Q ) s u c h t h a t n - L ( f ) : n - L ( T )
Let Gi: (N,, 7,,Pr,S;)for aIl i : l, ..., n, then: q : ( N,, Ti, 4 ' S,)for all i: l, "', n, where:
N , : { < A ,x > : A - ) r € P , } u { S r } ,
4'))' j;;:, :-::,,^-l;J"':;:-:;: ;" ri(a) : {a} for all a e Ti; r1(A) : {<A, x>: A -, x e P;} for all A e Ni.
Cluim 1. Let f be any n-MGN, let f be any n-MGR and let n-L(f) : n-L(f ). Then, LAD : LAf ;, for eachX e {union, conc,first}.
Proof.
Theorem 1. The classof languagesgeneratedby n-MGN in the X mode, where X e {union, conc,first} is equivalentto the classof languagegeneratedby n-MGR in the X mode.
Proof. This follows from Algorithm l, Algorithm2 andClaim l.
Algorithm 3. Conversionof n-MGR in the concatenationmode to matrix grammar o Input' z-MGR f : (Gr, Gz,..., G,, Q)
Outpzf.' Matrix grammarH: (G, M) such thatL,o,.(f): L(m
Let Gi: (N,, Ti,Pi, Sr)for all i : l, ..., n, andlet for anyj, k : 1,..., fl, whereT + ft holds: N1n Np: A; S € N' Then:
G : (N, T, P, 8, where:
N : { s }, , ! N) ; r :
l , r , t P : {s:S -+ S1S2..S. ,}u ( [J 4 );
j=l
M : { t } w { p r p z . . . p n( p: sp z ,. . . ,p , ) e Q } .
Algorithm 4. Conversionof n-MGR in the first mode to matrix grammar o Input' zr-MGRf : (Gr, Gz,..., G,, Q)
Output: Matrix grammarH: (G, rty')suchthatLp,t(f): L(ID
Let G; : (Nj, Ti,Pi,,S,)for all i : 1, ..., n, andlet for anyj, k : 1,..., fr, whereT * ft holds: I,{1a N1,: A; S € /{. Then: G : (N, T, P, S, where: ,!] t, ) t (!J{ ) to
l_tn ' t,=Ur;rh(A:) 7 fotalAI e 9*,t M : { s ) w { p , p r . . . p , t( p t ,p z , . . . ,p , ) e Q } .
N : { , St}/ N rt ( U { A :A . N , }) ; T : T ;
i=2
P : { s: ,S-> Srft(S2).. h(
Algorithm 5. Conversion of n-MGR in the union mode to matrix grammar o Input' n-MGR f : (Gt, Gz,..., Gn,Q)
Output: Matrix grammarH: (G,Iy') suchthatLunion(D: L(m
Let G1: (Nl, Ti,Pi, S) for all i : 1, ..., n, andlet for anyj, k: 1,...,fr, whereT * k holds:N,n Nr: A; S e N7.Then: G: (N, T, P, S), where:
M : { , st} ( Ui=l N ,) , { lj=)l t V :AeN , } ) T;: li=)l r , t
P : {
s1:,S) ,Srft(S2..).h(
Y' j=r i=r h(A) : V for all M : { t t , s 2 ,. . . ,s r } U { p , F r . . . F ,(i p vP z ,. . . , P r )e Q } defined as:h(a): e for all a el)f,t
i=l n t n
U * ' t j=l v { P , P r . . . P ,(:P r ,P z ," ' , P , ) e Q } Theorem2,For everyn-MGR in the Xmode, whereX e {union, conc,firsl}, thereis an equivalentmatrix grammar.
Proof. This follows from Algorithm 3, Algorithm 4 andAlgorithm 5.
Algorithm 6. Conversionof matrix grarnmarto 2-MGR o Input' Matrix grammarH: (G,i1); string w eT., where Iis any alphabet . Output:2-MGR f : (Gr, Gz,Q); {wt: (wt, ,) e z-L(f)} - L(m o Method:
Let G: (N, T, P, 8, then: G t : G ; Gz: (Nz,Tz,Pz,S2),where:
N z : { S z }v { < p p z . . . p k , j > i p t p z . . . p rM, e,l S j < k - t ) ; T z : T ; P z : { S z 1 < p p z . . .p p , l } : p r p z . . . p re, M , k > - 2 } w {<prpr...P rj>, + <PtPz'P..t,j+l', prpr....Per,M, k> 2, | <j < k-z)} v {<prpr...pr,k-l> -) 52:ppz...pr e M, k>2} v { S z+ S zp: t . M , l p | : 1 } u {<ptpr...pr,k-l> -+ w i prpz...pre M, k>2} w { S z- + f r , p , e M , l p r l : 1 } ; Q : {(pr,Sz-+<prpz..p.r, l>): ptpz..p.r e M, k>2} w {(pi*t,<PrPz".Pr,)P <Ptpz...pk,i+l>p):tpr..P'.r e M, k> 2, | <i < k-2} w {(pr,<ptpz...pr,k,-l> + 52):prpz...Pre, M, k>-2} w { ( p v S z + S 2 ) p: r e M , l p t l : 1 } u {(pr,<prpz...prk,-,l> -+ w): prpr...pr€, M, k>2} w { ( p ' , s z - - >w ) , p t e M ' l p ' t l: 1 } .
Claim 2. For every matrix grammar H, there is an equivalent 2-MGR in the concatenationmode.
Proof. Use Algorithm 6 with matrix grammar H and w : e in the input. Claim 3. For every matrix granrmar H, there is an equivalent 2-MGR in the first mode.
Proof. Use Algorithm 6 with matrix grammarH andany string w eT" in the input. * Ctuim 4. For every matrix grammar H, there is an equivalent 2-MGR in the union mode.
Proof. Use Algorithm 6 with matrix grarnmarH and w in the input, where w is any string in L(l-l), provided thatL(H) is nonempty.Otherwise, w is any string. Theorem.S.For every matrix grailrmar,there is an equivalent2-MGR in the X mode, whereX e {union,conc,first}.
Proof. This follows from Claim 2, Claim 3 and Claim 4.
Let .4(n-MGNx) and /(n-MGRx) denotethe languagefamilies defined by n-MGN in theX mode and n-MGR in the X mode, respectively,whereX e {union, conc,first} , let /(H) denote the family of languagesgeneratedby matrix grammars.From the previousresults,we obtain: .
4 H ) : . 4 ( i - M G N r , i > 2 .
. .1(H):.4(i-MGRx), i > 2.