I Introduction

The formal language theory has intensively investigated various grammar systems (see [1], l2l, [8]), which consist of several cooperating components, usually represented by grammars. Although this variety is extremely broad, all these grammar systems always use a derivation that generates a single string. In this paper, however, we introduce grammar systems that simultaneously generate several strings, which are subsequently composed in a single string by some common string operation, such as concatenation.

More precisely, for a positive integer n, an r-multigenerative grammar system discussed in this paper works with n context-free grarnmatical components in a general way-{hat is, in every derivation step, each of these components rewrites 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 generates n strings, out of which the strings that belong to the generated language are made by some basic operations. Specifically, these operations include union, concatenation and a selection of the string generated by 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. Besides this fundamental result, we give several transformation algorithms of these multigenerative grammar systems.

Preliminaries

This paper assumes that the reader is familiar with the formal language theory (see [4]). For a set, Q, carcl(Q) denotes the cardinality of Q. For an alphabet, V, f represents the free monoid generated by V under the operation of concatenation. The unit of I is denoted by e. Set I/ : I -{e}; algebraically, X rs thus the free semigroup generated by Zunder the operation of concatenation.

A context-free grammar 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 denotes the 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 language of G, L(G),is defined as L(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 grammar andM isafinitelanguageoveralphabetP,Mc.P'. Letx6, xt,...,xne(l',1 u T)-for any n ) 0, xi-1 ) xi lpil in G for all i: l, ..., n and ppz...pn e M. Then matrix grammar H makes direct derivation step from xsto xr, denoted zIS xs :> xn. Let =. denote the transitive-reflexive closure of =. The language of H, L(H), is defined as L(11): {w: S 3* w in H, for some * e t'y.

3 Definitions Dejinition 1. An n-multigenerative nonterminal-synchronized grammar system (n-MGN) is an n+l tuple, f : (Gr, Gz, ..., Gn, Q), where Gi: (Ni, Ti, Pi, S,) is a context-free grammar for each i: l, ...,, n, and Q rs a finite set of n-tuples of the form (At, Ar, ..., An), where Ai e Ni for all i: t, ..., n. Then, a sentential n-form of n-MGN is an z-tuple of the form X: (xv xz, ..., xn), where xi e (Niv-1 T)' for all i : I, ...) n.Let y: (urAp1, u2A2y2, ..., u,Anv) and 7 :

(uppy u2x2r2, ..., u,&rrr) be two sentential n-fotm, where Ai e Ni, Lti, vi, x; e (//, t-r Z;). for all i : 1, ..., n. Let Ai -+ xi € Pifor all i : I, ..., n and (At, A2, ..., Ar) 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-language of f , n-L(f), is defined as n-L(f): {(wr, w2,...,w,):(S,,Sr,...,S,,)=*(r,, wz,...,w,),w,e T1* forall i:7,...,n}.

The language generated byl in the union mode, Lu,io,(l), is defined as Lunion(l): {w: (wr, wr, ..., wn) e n-L(l), w e {wi: i: l, ..., n)}.

The language generated by I in the concatenation mode, L"on,(f), is defined as where Gi: (Ni, Ti, Pi, S,) is a context-free grammar for each i: l, ..., fl, and Q is a finite set of n-tuples of the form (pt,pr, ...,pn), where pi e Pt for all i: l, ...,fl.A sentential n-form for n-MGR is defined as the sentential n-form for an n-MGN. Let y : (utA1r1, u2A2r2, ..., u,y'4rt ) and X : (utxp1, u2x2v2, ..., u,{nvr) are two sentential nform, where Ai € 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, denoted by X =

X. An n-Ianguage for any n-MGR is defined as the n-Ianguage for any n-MGN, and a language generated by n-MGN in the X mode, for each X e {union, conc, first}, is def,rned as the language generated by n-MGR in the X mode. 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 {Sr}, :-::,, ^-l;J"';-: : :;: ;" j;;:, 4' ) )' Lp^'(l ).

Theorem 1. The class of languages generated by n-MGN in the X mode, where X e {union, conc, first} is equivalent to the class of language generated by n-MGR in the X mode.

Proof. This follows from Algorithm l, Algorithm2 and Claim l. . N: {s} , ,! N ); r: l,r,t Convention: Let p: A -> x be a rule. Then, label p denotes rule h(A) --> h(x).

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, where X e {union,conc,first}.

Proof. This follows from Claim 2, Claim 3 and Claim 4.

Conclusion

Let .4(n-MGNx) and /(n-MGRx) denote the language families 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 languages generated by matrix grammars. From the previous results, we obtain: . 4H):.4(i-MGNr,i>2. .

.1(H) :.4(i-MGRx), i > 2.