=Paper=
{{Paper
|id=Vol-255/paper-6
|storemode=property
|title=General Multigenerative Grammar Systems
|pdfUrl=https://ceur-ws.org/Vol-255/paper06.pdf
|volume=Vol-255
|dblpUrl=https://dblp.org/rec/conf/isim/LukasM07
}}
==General Multigenerative Grammar Systems==
https://ceur-ws.org/Vol-255/paper06.pdf
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