| Submission Procedure |
|
|
|
|||||||||||||||
A Variant of Team Cooperation in Grammar Systems
Technical University Wien, Institute for Computer Languages Resselgasse 3, 1040 Wien, Austria freund@csdec1.tuwien.ac.at
Institute of Mathematics of the Romanian Academy of Sciences PO Box 1-764, 70700 Bucuresti, Romania gpaun@imar.ro (Research carried out during the author's visit at the Technical University Wien) Abstract: We prove that grammar systems with (prescribed or free) teams (of constant size at least two or arbitrary size) working as long as they can do, characterize the family of languages generated by (context-free) matrix grammars with appearance checking; in this way, the results in [Paun, Rozenberg 1994] are completed and improved. Keywords: Formal languages, grammar systems, teams 1 Introduction
A cooperating grammar system, as introduced in [Csuhaj-Varjù, Dassow 1990]
and [Meersman, Rozenberg 1978], consists of several (usually context-free)
grammars, each of them working, by turns, on a common sentential form. A
basic protocol of cooperation is the maximal competence strategy: a
component must rewrite the current sentential form as long as it can do this
(and hence never can finish, if it can work forever). In [Csuhaj-Varjù,
Dassow 1990] it is proved that in this way exactly the family of In [Kari, Mateescu, Paun, Salomaa 1994], a way to increase the power of cooperating grammar systems has been proposed: the cooperation of the components of a grammar system is increased by allowing (or forcing) some of the components of the system to work simultaneously in teams on the current sentential form in parallel, i.e. in each step, every member of the currently active team has to apply Page 105 a rule. In [Kari, Mateescu,
Paun, Salomaa 1994], the condition for a team to stop its work has been
the following one: no rule of any member of the team can be used any more.
Even with such a strong stop condition, non- Another stop condition has been considered in [Paun, Rozenberg 1994]: a team stops working if and only if at least one of its members cannot apply one of its rules any more. For this stop condition as well as for that introduced in [Kari, Mateescu, Paun, Salomaa 1994], in [Paun, Rozenberg 1994] it is proved that both using prescribed teams (all of them being of given size or of free size) and using free teams (of given size at least two or of arbitrary size at least two) exactly the family of languages generated by matrix (or programmed) grammars with appearance checking is obtained (thus strenghtening the results proved in [Csuhaj-Varjù, Paun 1993] and [Kari, Mateescu, Paun, Salomaa 1994]). The stop conditions considered in [Paun, Rozenberg 1994] are not the
natural extension of the maximal competence strategy from individual
components of grammar systems to teams of components: the simplest way for
such an extension is to allow a team to become inactive when it is no longer
able to rewrite the current sentential form as a team, irrespective
whether or not some or even all rules of the components can be applied
further. For instance, if the current string contains only two occurences of
the non-terminal A and we have a team consisting of three components, each
consisting of rules of the form There is also another reason for considering the new stop condition, namely a mathematical one: grouping sets of rules in teams may remind us of the mode of working of matrix grammars; checking whether rules in a component of a team can be applied may remind us of the appearance checking in matrix grammars. All together, these aspects make the following result somehow non-surprising (although the proof given in [Paun, Rozenberg 1994] is, by no means, obvious): grammar systems with teams (prescribed or free and of given size at least two or of free size at least two) working with the stop conditions considered in [Paun, Rozenberg 1994] characterize the family of languages generated by (context-free) matrix grammars with appearance checking. The new mode of stopping the work of a team is not related to the appearance checking manner of work in such an obvious manner, yet again all languages generated by matrix grammars with appearance checking can be obtained by grammar systems with free teams of given size at least two, but also with free teams of arbitrary size, which is an improvement of the results obtained in [Paun, Rozenberg 1994]. The study of teams, in general the study of classes of grammar systems in which both the sequential and the parallel modes of working are present, requests and deserves further efforts (see also [Csuhaj-Varjù 1994] for motivations of such investigations). Page 106 2 Preliminary definitions
We specify only a few notions and notations here; the reader is referred to [Salomaa 1973] for other elements of formal language theory we shall use and to [Dassow, Paun 1989] for the area of regulated rewriting. For an alphabet A matrix grammar (with appearance checking) is a construct
where For By
where A cooperating distributed grammar system (CD grammar system for short) is a construct
where
Given Page 107 An important derivation relation for CD grammar systems is the maximal
derivation mode
(such a derivation is maximal in the component
The family of languages generated in this mode by CD grammar systems with
3 Teams in cooperating grammar systems
In [Kari, Mateescu, Paun, Salomaa 1994] the following extension of CD grammar systems is introduced: A CD grammar system with (prescribed) teams (of variable size) is a construct
where
(the team is a set, hence no ordering of the components is assumed). In [Kari, Mateescu, Paun, Salomaa 1994] the following rule of finishing
the work of a team
(No rule of any component of the team can be applied to Another variant is proposed in [Paun, Rozenberg 1994]: Page 108
(There is a component of the team that cannot rewrite any symbol of the current string.) The language generated by If all teams in
where By As we are interested in the relations with the family In [Paun, Rozenberg 1994] it is proved that for all
The relations
The language generated by the CD grammar system Page 109 free teams of given size Obviously, if In order to elucidate some of the specific features of the derivation modes Example 1. Let
be a CD grammar system with the sets of rules
Obviously, If we consider
i.e. if we take the CD grammar system with prescribed teams
then we obtain
because
for Page 110 the derivation is blocked, although the stop condition for the derivation
mode As only teams of size at most two can be applied to a string of length two, we also obtain
Example 2. Let
be a CD grammar system with the sets of rules
If we consider
i.e. if we take the CD grammar system with prescribed teams
then we obtain
for Whereas for Page 111 4 The power of the derivation mode
In this section we shall prove that CD grammar systems with (prescribed or
free) teams (of given size at least two respectively of arbitrary size)
together with the derivation mode The following relations are obvious: Lemma 1. For all
Lemma 2. Proof. Let
with
consider all sequences of rules of the form
such that from each set
be all such sequences associated with the team Then
and
Page 112
The set The derivation starts form
corresponds to a derivation step in
at least one A similar construction like that elaborated above shows that for a CD grammar system with prescribed teams and arbitrary context-free rules we can construct a matrix grammar
with arbitrary context-free rules such that Page 113 Lemma 3. Proof. Let
where The family
Without loss of generality we may also assume that
where We take such a matrix grammar Assume all matrices of the forms
Now consider the following sets of symbols
Page 114
We construct a CD grammar system
and the components
Let us give some remarks on these constructions:
We now show that Claim 1. As the ´short strings´ in If
by a matrix
and no more step is possible with this team
Now, also in two steps, we obtain
In a similar way, if for a terminal string
by a matrix
and
i.e.
If
by a matrix
Page 116 Observe that from Using legal teams, i.e. the teams
Claim 2. Starting from an arbitrary legal configuration, every illegal team will introduce the symbol #. First of all we have to notice that in the following we can restrict our
attention to components associated with some matrix from For the rest of possible illegal teams of size two we consider the following three cases according to the three types of legal configurations: Case 1: Configuration
Page 117 In all cases, further derivations are blocked (they never can lead to terminal strings) because the trap-symbol # has been forced to be introduced. Case 2: Configuration
Case 3: Configuration Page 118 The only components that do not introduce
In conclusion, only the legal teams can be used without introducing the trap
symbol Now let
In contrast to the
and matrices of the form e can also be of the forms
Assume all matrices of the forms
Page 119 Now consider the following sets of symbols
We construct a CD grammar system
and the components
The intended legal teams of two components again are
In contrast to the Page 120 using appropriate teams of size 2 from Similar arguments as in the Lemma 4. Proof. For a language As in the previous proof we still have to notice that in the following we
can restrict our attention to teams where all components are associated with
matrices from only one set As the legal teams of two components again are
As teams of type Case 1: Configuration Each component being of one of the types
In all cases, further derivations are blocked (they never can lead to terminal strings), because the trap-symbol # has been forced to be introduced. Case 2: Configuration The only components that do not introduce # by the first rule to be
applied are
Case 3: Configuration The only components that do not introduce # by the first rule they can
apply are and Page 125
While In conclusion, again we have proved that only the legal teams can be used without introducing the trap symbol #, which completes the proof. Lemma 5. Proof. Let
We can construct a CD grammar system Page 126 Assume all matrices of the forms
Now consider the following sets of symbols
We construct a CD grammar system
The intended legal teams of two components again are
for arbitrary labels
Again we obtain As the additional components of type R contain the trap rules The family As it is quite obvious, the proofs of the preceeding lemmas cannot be used
for obtaining the results proved in [Paun, Rozenberg 1994] for the
derivation mode Page 128 an improvement of these results, because we now can allow teams of arbitrary size without the restriction for these teams to be of size at least two. Corollary. For every
Proof. As we have already pointed out in the previous section, Combining the main results obtained in this paper we get the following Theorem. For every
Proof. For the derivation mode For the derivation mode References
[Csuhaj-Varjù 1994] Csuhaj-Varjù E.: ´Cooperating Grammar Systems: Power and Parameters´; in: Results and Trends in Theoretical Computer Science (Kar J., Maurer, H., Rozenberg, G., eds.), LNCS, 812, 67 - 84; Springer-Verlag, Berlin (1994). [Csuhaj-Varjù, Dassow 1990] Csuhaj-Varjù E., Dassow, J.: ´On Cooperating/Distributed Grammar Systems´; J. Inform. Process. Cybern. EIK 26 (1990), 49-63. Page 129 [Csuhaj-Varjù Dassow, Kelemen, Paun 1994] Csuhaj-Varjù E., Dassow, J., Kelemen, J., Paun, Gh.: ´Grammar Systems´; Gordon and Breach, London (1994). [Csuhaj-Varjù, Paun 1993] Csuhaj-Varjù E., Paun, Gh.: ´Limiting the Size of Teams in Cooperating Grammar Systems´; Bulletin of the EATCS, 51 (1993), 198-202. [Dassow, Paun 1989] Dassow, J., P aun, Gh.: ´Regulated Rewriting in Formal Language Theory´; Springer-Verlag, Berlin (1989). [Kari, Mateescu, Paun, Salomaa 1994] Kari, L., Mateescu, A., Paun, Gh., Salomaa, A.: ´Teams in Cooperating Grammar Systems´; J. Experimental and Theoretical AI, to appear. [Meersman, Rozenberg 1978] Meersman, R., Rozenberg, G.: ´Cooperating Grammar Systems´; Proceedings MFCS'78, LNCS, 64, Springer-Verlag, Berlin (1978), 364-374. [Paun, Rozenberg 1994] Paun, Gh., Rozenberg, G.: ´Prescribed Teams of Grammars´; Acta Informatica, to appear. [Salomaa 1973] Salomaa, A.: ´Formal Languages´; Academic Press, New York (1973). Page 130
|
|||||||||||||||||
-languages can be obtained. In [
only, then none of
the conditions investigated in [
, by 
we denote the free monoid generated by 
under the operation of concatenation; the empty string is denoted by 
,
and 
is denoted by 
. The length of 
is denoted by 
, and for any
denotes the number of occurrences of symbols 
in 
.
and 
are disjoint alphabets ( 
is the nonterminal alphabet,
is the terminal alphabet), 
is the axiom, and 
is a finite
set of sequences (called matrices) of the form 
being a
context-free rule over 
with 
and
and 
is a subset of the rules occurring in the matrices of
.
we write 
if there are
strings 
in 
and a matrix 
in 
such that 
and for each 
with 
either
and 
or 
, the rule 
is not applicable to 
, and 
appears in 
.
(In words, all the rules in a matrix are applied, one after the other in
the given sequence, possibly skipping the rules appearing in 
, then the
grammar is said to be without appearance checking (and the component
can be omitted).
we denote the families of languages
generated by matrix grammars with arbitrary context-free respectively
and 
denote the families of context-sensitive respectively
recursively enumerable languages and 
denotes the family of
-free 
and 
are disjoint alphabets ( 
is the nonterminal alphabet, 
is the axiom, and
are finite sets of context-free rules over 
and are
called the components of the system 
.
For each component 
in the CD grammar system 
we denote
and 
we write 
if 
can be derived from 
by using a rule in 
in the usual sense: 
and 
. By 
and
we denote the transitive respectively the
reflexive transitive closure of 
.
(see [
i.e.
no further step can be done). The language generated by the CD grammar
system 
in the maximal derivation mode 
is defined by
-free rules is denoted by 
. From [
.
is a usual CD grammar system and 
the sets 
are called teams and are used in derivations as follows:
For 
and 
we write
has
been considered:
.)
in one of these modes is denoted by 
and 
respectively.
have the same size, then we say that 
then we cannot rewrite an axiom consisting of
one symbol only, hence we must start from a string or a set of strings as
axioms. Therefore, we consider systems of the form
is a finite set; the terminal strings of
are directly added to the language generated by 
. The others are
used as starting points for derivations. The languages generated by such a
system 
are denoted by 
and 
,
respectively; when free teams
of arbitrary size are allowed, we write 
respectively 
and if these free teams must be of size at least two,
we write 
respectively 
.
we denote the family of languages generated in the mode 
by CD grammar systems with prescribed teams of
constant size 
and 
-free context-free rules; if the size is not
constant we replace 
.
If the teams are not prescribed, we remove the letter 
, thus obtaining
the families 
, and 
, respectively.
,
too, we also consider CD grammar systems with prescribed (arbitrary) teams
of constant size 
(arbitrary size, of size at least two) and arbitrary
context-free rules; the corresponding families of languages generated in the
mode 
by such CD grammar systems are denoted
by 
and 
respectively.
and 
and 
as
defined in [
from components to teams. Such an
extension looks as follows (where 
are
as above):
in this mode 
is denoted by 
the languages generated by such a system 
in the mode 
when using
free
teams of arbitrary size, free teams of size at least two are denoted by
and 
,
respectively.
then 
too, but, as we have pointed out
in the introduction, the converse is not true; we can have 
without having
for 
. Consequently,
without necessarily having an
equality; the same holds true for the languages
and 
. This means that
we have no
relations directly following from definitions, between families considered
above and the corresponding families 
However, in the following section we shall prove that again a
characterization of the families 
and 
is
obtained, hence the new termination mode of team work is equally powerful as
those considered in [
we consider some examples. The first
example shows that the inclusions,
can be proper:
because the only way to get rid of
the symbol 
is to apply the rule 
from 
but because
of the rule 
the derivation can never terminate.
together with the prescribed teams (of size 2 )
yet still
because after one derivation step with 
i.e. 
cannot be applied
as a team any more to 
although the rule 
which is in
both sets of rules of the team 
is applicable to 
. This means that
is not fulfilled!
together with the prescribed teams (of size 2)
. Although this non-context-free language
is obtained in each derivation mode
the intermediate sentential forms
(after an application of
) are not the same:
the intermediate sentential forms
are 
and 
with 
in the
derivation mode 
we also obtain 
. These strings are somehow
hidden in the other derivation modes 
and 
because they can be
derived from a sentential form 
or 
with a suitable 
by using the derivation relation 
of the team 
but then further derivations with the team 
are blocked, although the stop conditions of the derivation modes 
respectively 
are not fulfilled. This additional control on the
possible sentential forms is not present with the derivation mode 
where a derivation using a team stops if and only if the team cannot
be applied as a team any more, which does not say anything about the
applicability of the rules in the components of the team on the current
sentential form. Nethertheless the same generative power as with the
derivation modes 
and 
can be obtained by teams using the
derivation mode 
too, which will be shown in the succeeding section.
again yield characterizations of the
families 
respectively 
.
we have
be a CD grammar system with prescribed teams and 
-free rules. We construct a matrix grammar
-free rules as follows.
For a team
exactly one rule is present in 
. Let
.
is obtained by replacing each nonterminal in 
by its primed version, 
contains all rules of the form 
in the previous
matrices.
In general, from a sentential
form 
in a non-deterministic way we can pass to 
in order to start the simulation of the team 
.
Using a matrix
(the primed symbols in 
ensure the parallel mode of using the rules
The primed symbols can be
replaced freely by their originals using the matrices 
The symbol 
can be changed only by
passing through 
which checks the correct
termination of the derivation in 
in the sense of the mode 
of
derivation: we can pass from 
to 
if and only
if the corresponding sequence 
of rules cannot be used
(otherwise a symbol 
will be introduced, because for each sequence
is 
). After obtaining a sequence 
we introduce the symbol 
which is replaced by 
only after having replaced all primed symbols 
with 
by their original 
. Then we can pass to checking the sequence 
If none of the sequences 
can
be used, we can introduce the symbol 
and then 
in this way
the derivation in 
is successfully simulated, and we can pass, in a
non-deterministic way, to another team.
When the matrix 
is used, the string must not contain any
further non-terminal, because no matrix can be used any more.
In conclusion, 
As 
is
closed under right derivative, it follows that 
.
; observe
that we do not need the additional terminal symbol 
because in the case
of arbitrary context-free rules we can simply replace the matrix 
by the matrix 
. As an immediate
consequence, we obtain 
.
be a matrix language in 
. We
can write
denotes the right derivative of 
with respect to
the string 
.
is closed under right derivative, hence 
For each 
let 
be a
matrix grammar for 
and moreover, we suppose that 
is
in the accurrate normal form [
where 
are pairwise disjoint.
are of one of the following forms:
consists of all rules 
appearing in
matrices of 
.
and 
in matrices of the forms 
(if we have a matrix 
with 
or 
we can replace it by the sequence of
matrices
as well as 
and 
with 
are new symbols to be added to 
and
respectively); in a similar way, we can assume that 
in a
matrix 
of form 
(a matrix
can be replaced by the matrices 
and 
where 
is a new symbol to be added to 
).
for every language 
without loss of generality, we may assume that the
sets 
are pairwise disjoint.
in the sets 
to be labelled in a one-to-one manner such that the labels used for 
and
let 
be the set of all the
corresponding labels as well as
with 
as the set of non-terminal symbols, 
as the set of terminal symbols, the set of axioms
for 
constructed as follows:
is a matrix of type
with 
and 
then we take the components
is a matrix of type
with
then we take the components
is a matrix of type 
(hence with 
), with
,then we take the components
and
for
arbitrary labels 
(which would already solve the problem for
prescribed teams of size two); all other pairs of components cannot work in
the mode 
without introducing the trap-symbol #.
for ´almost all´ symbols 
the
termination of a derivation sequence with a legal team is only guaranteed by
the "exceptions" in the components of type 
.
as well as subscripts added to symbols in 
(leading to
symbols in 
and to symbols in 
(leading to symbols in 
with free teams of constant size two
in the same way as with the prescribed teams of size two described above generates 
:
are directly introduced in 
it is enough
to prove that every derivation step in a grammar 
can be simulated by
the teams of 
More exactly, we shall prove that if 
is a derivation step in 
,where 
is
not a terminal string, then 
,and that if 
is a terminal string, then 
in a derivation sequence using teams of size 2 from 
.
of type 
then
,hence
of type 
, then we obtain
of type 
, then
no further derivation step with the team
is possible if and only if 
.
In conclusion, every derivation in a grammar 
can be simulated in 
by applying a suitable sequence of appropriate teams of
pairs of components, which completes the proof of claim 1.
and 
we can only obtain the following sentential forms not containing the trap symbol
# (we call them legal configurations):
,because
components associated with some matrix from 
with 
already at the first
application of a rule force us to introduce the trap symbol #. For the same reasons, we need not take into account teams consisting of two components of type Q:
they cannot work together without introducing #, because they can only replace symbols in 
by symbols different from #.
,i.e. of type 1.
Each component being of one of the types 
and 
will
introduce # at the first application of a rule; therefore it only remains
to consider pairs of components of the types 
and 
, for
different labels from 
associated with matrices from 
( the label
must be different, because otherwise either the team were legal or else the
teams would not be of size two). Hence only the following teams might be
possible:
, where 
: The intermediate strings coming up
during the application of such a team will contain at least one symbol
or 
as well as at least one symbol 
or 
for the two different labels 
and 
, hence before the derivation with the team can terminate,
at least one of the rules of the form 
(i. e. 
respectively 
or 
)is forced to be applied in at least one of the components.
, where 
: While the component 
works on symbols from 
,
the other component 
intoduces at least one symbol 
.
As 
contains all rules 
for 
(and no other rules for 
) and
contains all rules 
for 
(and no other rules for 
), the derivation with the team 
cannot terminate without a step introducing the symbol #
by at least one of the components.
The only components that may not be forced to introduce # by the first
rule they can apply are 
for any arbitrary 
as well as
and
Hence only the following teams might be possible:
where 
(otherwise the team would not be of size two):
will introduce some 
and 
will introduce some
,therefore further derivations are blocked by introducing the trap symbol # with 
(in two or three steps) can replace 
and 
in the meantime 
must introduce some 
then from 
in two steps (if a second step in
is possible without introducing #) we obtain 
, where
,then in the third step at least 
now must use a rule introducing the trap symbol #, e.g. 
whereas 
if not also being forced to use such a trap rule, may be able to use
once again or 
if it just happens that 
is the right symbol from 
that can be handled by 
.
, then 
or 
from 
can be applied in the third step, but even if 
can replace a third occurrence of 
, at least in the fourth step 
now is forced to introduce the trap symbol #, e.g. by 
.
i.e. if we use the team 
, then again we have to distinguish between two subcases:
, then 
can replace all occurences of 
by 
, while 
can replace 
.
As we have assumed 
, no other rule not introducing # than 
can be used in 
. Moreover we also
have assumed the rule 
to be non-recursive i.e. 
,hence after a finite number of derivation steps with the team 
the occurrences of 
will be exhausted, so finally a rule introducing the trap symbol # must be used by 
(one possible candidate is 
, while 
can use 
(if this rule has not yet been used before).
, we face a similar situation as above except that from 
two steps are needed in 
in
order to obtain 
from 
.
: While 
is used in 
must introduce some 
; if no more non-terminal symbol 
is available in the current sentential form, when 
uses its rule for replacing 
will have to use a trap rule like 
can introduce one more 
, then finally a trap rule like 
must be applied by at least one of the components 
and 
before the derivation can terminate.
by the first rule they can
apply are
for any arbitrary 
(and therefore
) as well as 
and
Hence only the following teams might be possible:
where 
(otherwise the team would not be of size
two):
will introduce some 
and
will introduce some
therefore further derivations are blocked by introducing the
trap symbol 
with 
can only
replace 
by
in the meantime
must introduce
some 
In the second derivation step, in 
the trap rule
can be used, whereas from 
at least 
can be applied.
While 
is used in 
must
introduce some 
but then 
has to use
a trap rule like
while 
can use 
once more or at least
; they simulate matrices in the sets 
hence also
the inclusion
is true, which completes the
proof of
be a matrix language in 
. As 
-rules are allowed in this case, we need not split up the language 
in languages 
hence, for a matrix grammar
with
we can directly construct a CD
grammar system 
such that 
Again the matrix
grammar
can be assumed to be in the accurrate normal form [
where 
are pairwise disjoint.
are of one of the following forms:
consists of all rules
appearing in
matrices of
-free case, matrices of the form 
can also be of the form
in the sets
to be labelled in a one-to-one manner and let 
be the sets of all the corresponding labels as well as
with 
as the set of non-terminal symbols, 
as the set of terminal symbols, the set of axioms
for
constructed like in the previous case:
is a matrix of type 
with 
and
for arbitrary labels
the legal configurations are
-free case we can use the 
in the component
associated with a
matrix
of type
which allows
us to avoid the splitting up of the language
into the right derivatives
yet again we obtain 
If is a derivation step in
where
is not a terminal string, then
in a
derivation sequence
and if 
is a terminal string, then 
in a
derivation sequence using the appropriate teams of size 2 from 
.
-free case can be used to
show that 
Hence again we obtain 
which proves 
too.
in
respectively 
we just take the adequate CD grammar system
already constructed
in the proof of the previous lemma. As the legal teams of size two still are
available, we obviously obtain 
On the other
hand, we still have
too, although the
possibilities for forming teams from the constructed components have
increased considerably. Yet we have to adapt our arguments according to this
new situation.
because components associated with some
matrix from another set of matrices
with
already at the first application of a rule force us to introduce the
trap symbol 
Hence in the following it is sufficient to consider the
case where 
in
and
for
appropriate labels
the legal configurations are
cannot work together without introducing #, because
they can only replace symbols in
by symbols different from #
we need not take into account teams containing at least two components of
type
. Moreover, every team of size one finally is forced to introduce
the trap symbol # when started on a legal configuration (i. e.
the result for
is the same as for
). Hence in the following we
now take a closer look on every possible combination of components yielding
a team with at least three components and allowing at least one derivation
step on the legal configurations listed above without introducing the trap symbol #:
i. e. of type 1.
and 
will
introduce # at the first application of a rule; therefore it only remains
to consider teams
where each component is of one of the types 
and
contains only components of the type where obviously
all labels of these components have to be different. Then at most one label
can be from 
because such a component only once can use the
rule 
, whereas all the other components 
with 
can also apply a rule to the symbol 
to any occurrence of the
corresponding symbol 
Hence, before the derivation with the team can
terminate, at least one of the rules of the form 
(e. g. 
or
) is forced to be
applied in at least one of the components.
contains exactly one component 
wheras all the other
components are of the type
i. e.
Denote
Again, at most one label in
can be from 
In the
first derivation step with the team
for 
respectively for
from 
is used, while at most one component 
can
use the rule
whereas all the others have to use the
rules
for the corresponding non-terminal symbols 
in the next step 
has to use a trap rule.
has been applied in the first step
(observe that
if
), then even if 
every component of 
can apply a rule,
i. e. for
we choose
for some
for
we can take
from 
at least 
can be applied, and in the remaining components 
at least
is
applicable.
has not been applied in the first
step, i. e. for each
the rule 
has been taken from 
(which implies
and therefore 
too), again a second
step with T is possible: We can choose
from
while at least
is applicable in the remaining
components 
then one more derivation
step may be possible without 
being forced to use a trap rule, but
again in any case the trap symbol
must be introduced before the
derivation can terminate, even if 
contains the legal team
i. e. 
then only one derivation step with
is possible without introducing
and in this step 
has used
the rule
whereas all the other
had to use
for the
corresponding symbols
and 
used 
now is forced to use a trap rule like
(observe that
), whereas 
can use its rule for replacing 
and the other components
at least can apply 
then at most two
derivation steps with the team
are possible without introducing the trap
symbol 
where at most once one component
can apply 
whereas otherwise the components 
have to
use the corresponding rules 
is possible, where
is forced to apply a trap rule, e.g. for 
we can choose
where 
such that
has
not been replaced by
whereas all the components 
can at least apply 
has been
possible, i.e. at least one component 
cannot apply a rule
not introducing
any more, then a second step with
is possible,
where 
uses
and
is forced to
apply a trap rule. If 
has not been replaced in the first derivation
step,
can apply 
while also the
other components
with
at least can use
if 
has
been applied in the first step, in the second step from
we
can choose
instead of
has been applied in the first step for some 
then we can choose
from 
from
at least 
can be
applied, while from 
at least
is applicable.
for any arbitrary
as well as
and 
Hence only the following teams
might be possible:
cannot replace the symbols 
without introducing 
hence they will introduce
and therefore
finally at least one component will have to use the trap rule 
While 
can replace
or
in the
first step, the components
can only use the
corresponding rules in order not to introduce
If some
cannot use a rule not introducing
any more
after this first step, at least this component is forced to use a trap rule
like
while also the other components 
can apply at least 
(and
can replace the symbol from
not
affected in the first step). If two steps without introducing
are
possible with the team
then all together
symbols
have
been introduced. As 
these symbols guarantee that a trap rule must
be applied, before the derivation with
can terminate.
then 
can replace all occurrences
of 
by 
while
can replace 
by 
and
by 
As we have assumed 
no other rule not introducing 
than 
can be used in 
Moreover, as we also have
assumed the rule 
to be non-recursive, i. e. 
the occurrences of the symbol 
will be exhausted after a finite number of steps with the team 
so
finally at least 
will be forced to use a trap rule. The other
components 
in the first
step can only apply the corresponding rules 
and in
the succeeding steps one of these components once also might be able to
apply a rule to 
be the number of steps that are possible with the team 
without introducing #. If 
then 
has replaced 
by 
or 
by 
whereas all the components 
have introduced one symbol 
Hence, in the current sentential form 
symbols 
for 
are present
as well as 
and two symbols 
respectively 
and 
i. e. at least 
non-terminal symbols, which guarantees that a
second derivation step is possible, where at least one trap symbol 
is
introduced. If 
then at least one symbol from 
one
symbol from 
and 
symbols 
with 
occur in the current sentential form. As 
again another derivation step introducing # is possible in any case.
we face a similar situation except that for
we need two steps in order to obtain 
from 
by using 
in 
(i. e. the symbols 
cannot be ´consumed´ so fast by 
as in the previous case) and moreover, after one step the symbol
from 
may have vanished, so no other 
can use a
rule on a symbol from
Let 
again denote the number of
steps possible with 
without introducing
for all 
exactly 
symbols
appear
in
the current sentential form. For
which
guarantees that after these 
steps another derivation step introducing
the trap symbol # can be applied. For
we have at least 
such symbols as well as additional non-terminal symbols appearing in the
current sentential form, i. e. one symbol from
as well
as at least one symbol 
uses 
etc. the components 
can only apply the corresponding rules
Even if 
the symbol from 
can only
vanish in the third derivation step with the team
i. e. in
any case, after at most two (for
) respectively at most
three (for
) derivation steps without introducing 
we are forced to use a trap rule in a further derivation step, which is
always possible, because the number of non-terminal symbols in the current
sentential form in all cases is at least 
(observe that also for
we can always find a non-terminal symbol 
).
the legal subteam 
can only make two (for
)
respectively three (for
) derivation steps without
introducing #.
is possible,
besides 
and 
in
at least
non-terminal symbols must be present for allowing the components 
to use the corresponding rules
Even after applying 
respectively 
in 
at
least 
non-terminal symbols are left to guarantee another derivation
step, if at least one component is already forced to apply a trap rule after
the first derivation step.
Then at most a second derivation step without
introducing # is possible. After this second derivation step, again at
least
non-terminal symbols are left in the current sentential form:
in the first step from
in the second step again we may apply
but all
together we have 
non-terminal symbols from 
left in the
current sentential form, i. e. together with
and 
these
are 
non-terminal symbols allowing a third derivation step introducing 
in the first derivation step,
the current sentential form contains two symbols and 
symbols
for the labels 
as well as the control symbol 
Even if some 
can apply the rule
in the second step, 
has to use 
has to apply
(which consumes only one of the two
symbols 
), and all the other components 
have to use
so that
at least 
non-terminal symbols are left in the current
sentential form after two derivation steps, which again allows a third derivation step introducing #.
The only difference to the previous case is that
the components 
cannot generate
i. e. similar arguments like those used above show that the
derivation with the team cannot terminate without introducing the trap symbol #.
In this case, at most three derivation steps
without introducing
are possible.
if after the first derivation
step at least one component 
can only use a
trap rule, a further derivation step is possible, because at least 
non-terminal symbols are available in the current sentential form. Whereas
the components 
in every step ´produce´ a
non-terminal symbol 
can use
uses its rules on the symbols from 
After two steps, a symbol from 
is still occurring in the current sentential form, and 
can only have been responsible for the changing of 
to a terminal symbol.
is eliminated by 
has the possibility to have eliminated 
as well as one symbol
Yet in three steps by the components 
symbols
have been generated, which guarantees a fourth
step with introducing
to be possible before the derivation with the 
team can terminate.
for
some 
also shows the necessity of delaying the
generation of 
from
(i. e. 
being the label of a terminal matrix
), with two rules
and 
instead of using only one single rule 
for any arbitrary 
(and therefore
) as well as
Hence only the following teams might be possible:
introduces symbols 
until the
non-terminal symbols for at least one component are exhausted, therefore
finally one rule of the form 
has to be applied in at
least one of the components of the team.
can only replace 
in the meantime, the other
components
must introduce symbols
In the second derivation step, in
the trap rule
can be used, whereas all the other components at least can apply 
is used in 
the other components 
introduce symbols
but in the second
derivation step 
has to use a trap rule, e. g. 
while the other components 
at least can
apply 
uses 
and
uses
the other components
introduce symbols
now has to use a trap rule like
can apply at least some rule on 
and all the other components 
can at least apply
be a matrix language in
be a matrix grammar
with
Again the matrix grammar
can be assumed to be in the
strengthened accurrate normal form described in the preceeding two lemmas:
consists of all rules
appearing in matrices of
such that
using the ideas already known from the preceeding proofs for the case 
i. e. we add 
additional control variables in every
legal sentential form as well as 
in the sets
to be labelled in a one-to-one manner and let 
be the set of all the corresponding labels as well as
as the set of non-terminal symbols, 
as the set of terminal symbols, the set of axioms
the legal configurations are
is a derivation step in 
where
is not a
terminal string, then
in a derivation sequence using appropriate teams of
size
from
and if
is a terminal string, then
in a derivation sequence
using the appropriate teams of size 
for every 
these additional components
will never be responsible for the termination of a derivation sequence with
a team containing such components. Hence, similar arguments as in the
previous proofs can be used to show that 
thus again we obtain 
which proves
is closed under right derivation, hence 
For each of these languages
we consider a matrix grammar 
in
the strengthened accurrate normal form in order to construct a CD grammar
system 
following the ideas described
in the first part of this proof and of Lemma 3. The details of this
construction for proving
are obvious and
therefore left to the interested reader.
e. g. the components 
contain the rules
for every
which means that
still is applicable to every legal
configuration even after the termination of a derivation sequence with the
legal team 
On the other hand, the CD
grammar systems 
in the proofs of Lemma 3, Lemma 4 and Lemma 5 were
elaborated in such a way that they also work correctly in the dervation mode
which not only allows a new proof of some of the results already
obtained in [
for every
and every CD grammar system
Therefore this relation also holds true for the CD grammar systems 
constructed in the previous proofs for the matrix languages in 
Moreover, whenever
with a legal team
from
where
is a legal
configuration and
is a legal configuration or a terminal string, then
we also have
because in any case from the
component of type
in the team
no rule can be applied any more when
the derivation sequence started from
terminates with
according
to the derivation mode 
which implies that the derivation sequence
terminates in the derivation mode
too. Therefore we conclude which all together implies 
and completes the proof of the
corollary.
all the results stated in the
theorem follow from the results already proved in [
all the results stated in the theorem follow
from the results proved in this section: From Lemma 1 we know that
(respectively
) is an upper bound for
all the other families of languages generated by CD grammar systems (without
-rules) with teams in the derivation mode
and in Lemma 2 we
have proved 
(respectively 
). On the other hand, in
Lemma 3, in Lemma 4 and in Lemma 5 we have proved that 
for
every 
which all together proves the results stated in theorem.
