General Multigenerative Grammar Systems Roman Luk65r, Alexander Medunar ' Dept. of Information Systems,Faculty of Information Technology, Brno University of Technology,BoZetdchoval, 61266 Brno, CzechRepublic { lukas,meduna}@fit.vutbr.cz Abstract. This paper presents new models for generating matrix languages. These models are based on multigenerative grammar systems that simultaneously generateseveral strings in a parallel way. The components of these models are context-free grarrrmars, working in a general way. The rewritten nonterminalsare determinedby a finite set of nonterminal sequences. Keywords: Grammar system,matrix gralrlmar,generalderivation. I Introduction The formal language theory has intensively investigated various grammar systems (see [1], l2l, [8]), which consist of several cooperating components, usually representedby grammars.Although this variety is extremely broad, all thesegrammar systemsalways use a derivation that generatesa single string. In this paper, however, we introduce grammar systemsthat 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 system discussedin 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 language are made by some basic operations.Specifically, these operations include union, concatenationand a selectionof the string generatedby the first component. In this paper, we prove that all the multigenerative grammar systems under discussion characterize the family of languages, which is generated by matrix grammars.Besidesthis fundamentalresult, we give severaltransformationalgorithms of thesemultigenerativegrammar systems. 2 Preliminaries This paper assumesthat the reader is 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 operation of concatenation.The R. Lukdi and A. Meduna 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, where N 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 set of rules of the form A ) x, where A e l,'l and x c (N wT).. To declare that a label r denotesthe rule, we write as r: A-+ x.Letu, v e (Nu 7)'. For every r: 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 grammar H makes direct derivation step from xsto xr, denotedzISxs :> xn. Let =. denote the transitive-reflexiveclosure of =. The language of H, L(H), is defined asL(11): {w: S 3* w in H, for some* e t'y. 3 Definitions Dejinition 1. An n-multigenerative nonterminal-synchronizedgrammar system (n- MGN) is an n+l tuple, f : ( G r , G z ,. . . , G n ,Q ) , where Gi: (Ni, Ti, Pi, S,) is a context-freegrammarfor each i: l, ...,, n, and Q 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), wh e rex i e (N i v -1T )' fo r a l l i : I , ...) n.Let y: (urA p1,u2A 2y2, ..., u,A nv) and 7 : (uppy u2x2r2,..., u,&rrr) be two sententialn-fotm, where Ai e Ni, Lti,vi, x; e (//, t-r Z;).fo r a l l i : 1 , ..., n . L e t Ai -+ xi € P i for al l i : I, ..., n and(A t, A 2, ..., A r) e Q. Then X directly derives X in f, denoted by X = X. h the standard way, we generalize= to -k, k ) 0, 3*, and =*. The n-languageof f , n-L(f), is definedas n - L ( f ) : { ( w rw , 2 , . . . , w , ) : ( S , , S r , . . . , S , , ) = *w( rz,,,. . . , w , ) , w , T e 1f*o r a l li : 7 , . . . , n } . The languagegeneratedbyl in the union mode,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 defined as Lronr(l): {wtwz...wn: (w5 w2, ..., wn) e n-L(l)}. The languogegeneratedby I in thefirst mode,Lnn,(l), is defined as L p ,r,(l ): {w i (w r, w r, ..., w r) e n-L(l )| . General Multigenerative Grammar Systems 207 Example1. f : (Gr, Gz, Q), where Gr : ({Sr, I ,), {a, b, c}, {Sr -+ aS1,,S1-->aA6 A1 -->bA(, At -->bc\, Sr), Gz : ({Sz,Ar.}, {d}, {Sz-+ SzAz,Sz -) 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 } , Lro rr(l ): { a n b n c ' d 'n: ) | } , a n dL n^,(f): {anb' c' :n> l }. DeJinition 2. An n-multigenerative rule-synchronizedgrammar system (n-MGR) is n+l tuple f : ( G t , G z ,. . . , G * Q ) , where Gi: (Ni, Ti, Pi, S,) is a context-freegrammar for each i: l, ..., fl, and Q is a f in i te s e t o f n -tu p l e so f th e fo rm (pt,pr, ...,pn), w herepi e P t for al l i : l , ...,fl .A sententialn-form for n-MGR is defined as the sententialn-form for an n-MGN. Let y : (utA1r1,u2A2r2,..., u,y'4rt) and : (utxp1, u2x2v2, ..., u,{nvr)are two sententialn- X form, whereAi € Ni,Lti,ri,xi e (,M,u Ti)-for all i: 1, ...) n. Let pi: 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,rnedas the languagegeneratedby n-MGR in the X mode. E x a mp l e2 . f : (G t, Gz ,Q),w h ere Gr : ({ S t, A r} , { a, b, c}, {1: 51 -) rzS 1, 2: 51 -+ aA 1 ,3 :Ar -) --> -) b A p ,4 z A1 b c \, S r),Gz: ({ S z}, {d} , {l : ,S 2 S 2S 2,2z Sz-+ ,S 2,3: 52 -+ d|, Sz),Q : {(1, l), (2, 2), (3, 3), (4,3)}, is 2-multigenerativerule-slmchronized granrmarsystem.We have z-LQ): {(anb'cn,dn): n > 1}, Lunion(f): {anb'c':n> l} v { d ' : n > l } , L " o n " (f): { a ' b n c n { :n> | }, andLn,,,(f): { e' bnc' :n> l } . 3 Results Algorithm 1. Conversionof n-MGN to n-MGR t Input' n-MGN f : (Gt, Gz, ..., G,, Q) . Outpaf.'n-MGR f : (Gu Gz, ..., G,, Q ) suchthatn-L(f1: n-L(T) Method: Let Gi: (N,, Ti, Pi, S;) for all i : l, . . ., n, then: : { Qq r-) /r, Az -+ x 2 , ' .., A n ) xr):A i ) xi e P ; for al l i : 1, ..., n, and 0 ( A v A z , . . . , A ne) Q ) . 208 R. Lukdi and A. Meduna Algorithm 2. Conversionof n-MGR to n-MGN o Input' n-MGR f : (G', Gz, ..., Gn,Q) . O u tp z t..n -M G N f : 1G ,,Gr, ..., G,, Q)suchthat n-L(f) : n-L(T ) o Method: 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}, j;;:, 4'))' :: :;: ;" :-::,,^-l;J"';- ri(a) : {a} for all a e Ti; r1(A) : {: A -, x e P;} for all A e Ni. : -) rr, Az -) x2, ..., An ) 0 {G.qt, xt}, 1Az,x2}, ..., ): (Al xr) e Q} \J {(S', Sz, . . ., S,) } . : n-L(f Cluim 1. Let f be any n-MGN, let f be any n-MGR and let n-L(f) ). Then, LAD : LAf ;, for eachX e {union, conc,first}. Proof. L L,,ion(f): {r' (wr,wr, ...,wr) e n-L(T),w e{w; i: t, ...,n}}: {., (wr,wr, ..., w n ) e n - L ( T ) , , * e { w i : i : l , . . . , n } } : L u n i o n ( )f . I I . L r o n r ( f ) : { w t * r . . . w n t ( w r , w z , . . . , w n ) e n - L ( f ) } : { w r w z . . . w n :( w 5 w 2 , . . . , w n ) e n-L(T)) : L.-.(f ). I I L L T * , , ( f ) : { w , : ( w v w 2 , . . . , w n )e n - L ( f ) } : { w i ( w t , w r , . . . , w n )e n - L ( f ) } : Lp^'(l ). Theorem 1. The class of languagesgeneratedby n-MGN in the X mode, where X e {union, conc,first} is equivalent to the class of languagegeneratedby n-MGR in the X mode. Proof. This follows from Algorithm l, Algorithm2 and Claim l. . GeneralMultigenerativeGrammarSystems 209 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 that L,o,.(f): L(m o Method: Let Gi: (N,, Ti, Pi, Sr) for all i : l, ..., n, and let 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 ( 4 ); [J j=l M : { t } w { p r p z . . . p n( p: s p 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 grammar H: (G, rty')such that Lp,t(f): L(ID o Method: Let G; : (Nj, Ti, P i,,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: N: {,S}t/ Nrt (U {A: A. N,}); T: T; i=2 P : { s: ,S-> Srft(S2). .. h(5,) } u P1 u ,n (l)Vf , l -+ h(x): A -+ x e P,\), whereh ts a homomorphismfrom i-2 ,!] t, ) t (!J{ ) to as:h(a):erorall : Ae N,} defined l_tn ; h(A): 7 fotalIA e ' t,=Urr 9*,t M : { s ) w { p , p r . . . p , t( p t ,p z , . . . ,p , ) e Q } . Convention: Let p: A -> x be a rule. Then, label p denotesrule h(A) -->h(x). 210 R. Lukdi andA. Meduna Algorithm 5. Conversion of n-MGR in the union mode to matrix grammar o Input' n-MGR f : (Gt, Gz, ..., Gn,Q) . Output: Matrix grammar H: (G,Iy') such that Lunion(D: L(m c Method: 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} ( U N ,) , { l ) t V : A e N , } ) T li=l) r , t i=l j=l P: { s1:,S) .. h(5,),s2:S -) ,(,Sr)S2. ,Srft(S2). .. h(5,), ... s ,: ,S -+ ft(S r)ft(S 2)...S ) ,u (Uf ) u (gt f n - > h ( x ) : A - - > x e P , \w ) ,h e r eh i s a from(l'llr, ) u (Uq ) t" homomorphism ' j=r ; {V : A. N,} Y' i=r defined as: h(a): e for all a el)f,t h(A) : V for all i=l n nt U*'tj=l M : { t t , s 2 ,. . . ,s r } U { p , F r . . . F , (i p v P z ,. . . , P r )e Q } v { P , P r . . . P ,(: P r ,P z ," ' , P , ) e Q } \ - /. , . w { P r P r " ' P n (: P t 'P z ' " ' ' P ' ) e Q } ' Theorem 2,For every n-MGR in the Xmode, whereX e {union, conc,firsl}, thereis an equivalentmatrix grammar. Proof. This follows from Algorithm 3, Algorithm 4 and Algorithm 5. GrammarSystems GeneralMultigenerative 211 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: Gt: 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 j > + < P tP z' P { < p rp r...P r, .. t,j + l ' , prpr....Per, M, k> 2, | < j < k-z)} v { < p rp r...p r,k -l > -) 52:ppz...pr e M, k> 2} v { S z+ S zp: t . M , l p | : 1 } u { < p tp r...p r,k -l > -+ w i prpz...pre M, k> 2} w { S z- + f r , p , e M , l p r l : 1 } ; Q : { (p r,Sz -+< p rp z ... p r , l > ): ptpz...pr e M, k> 2} w { (p i * t,< PrP z " .Pr,P ): P. r e M, k> 2, | < i < k-2} w ) < P tpz...pk,i + l >ptpr..' k-l> + 52):prpz...Pr,e M, k>-2} w {(pr, -+ w ): prpr...pr,€ M, k> 2} w { (p r,< p rp z ...p r,, { ( 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 and any string w eT" in the input. * 212 R. Lukdi andA. Meduna Ctuim 4. For every matrix grammar H, there is an equivalent 2-MGR in the union mode. Proof. Use Algorithm 6 with matrix grarnmar H and w in the input, where w is any string in L(l-l), provided that L(H) is nonempty. Otherwise, w is any string. Theorem.S.For every matrix grailrmar,there is an equivalent 2-MGR in the X mode, whereX e {union,conc,first}. Proof. This follows from Claim 2, Claim 3 and Claim 4. 3 Conclusion Let .4(n-MGNx) and /(n-MGRx) denote the languagefamilies defined by n-MGN in the X mode and n-MGR in the X mode, respectively,where X e {union, conc,first} , let /(H) denote the family of languagesgeneratedby matrix grammars. From the previous results,we obtain: . 4H):.4(i-MGNr,i>2. . .1(H) :.4(i-MGRx), i > 2. References L Csuhaj-Varju,E., Dassow,J., Kelemen,J., Paun,Gh.: Grammar Systems:A Grammatical Approach to Distribution and Cooperation,Gordon and Breach, London (1994) 2. Dassow, J., Paun, Gh., and Rozenberg, G.: Grammar Systems, In Handbook of Formal Languages,Rozenberg,G. and Salomaa,A. (eds.),Volumes 2, Springer,Berlin (1997) 3. Harrison,Michael A.: Introductionto Formal LanguageTheory. Addison-Wesley,London ( l e78) 4. Meduna, A.: Automata and Languages:Theory and Applications, Springer, London (2000) 5. Meduna, A.: Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity,Acta Cybernetica(2003) 126-137 6. Paun, Gh., Salomaa, A. and S. Vicolov, S.: On the generative capacity of parallel communicating grammar systems. International Journal of Computer Mathematics 45, (tee2)4s-se 7. Salomaa,A.: Formal Languages,AcademicPress,New York (1973) 8. Vaszil, G.: On simulating Non-returningPC grammar systemswith retuming systems, TheoreticalComputerScience(209) l-2 (1998) 319-329