The aim of this note is to show how parallel communicating grammar
systems and concurrent programs might be viewed as related models for
distributed and cooperating computation. We argue that a grammar system can be
translated into a concurrent program, where one can make use of the
Owicki-Gries theory and other tools available in the theory of concurrent
programming. The converse translation is also possible and this turns out to be
useful when we are looking for a grammar system able to generate a given
language.
In order to show this, we use the language:
L
_{cd}
=
{a
^n
b
^m
c
^n
d
^m
∣
n,m ⩾ 1}, called crossed agreement language, one of the basic non-context
free constructions in natural and artificial languages. We prove, using tools
from concurrent programming theory, that L
_{cd}
can be
generated by a nonreturning parallel communicating grammar system with three
regular components. We also discuss the absence of strategies in the concurrent
programming theory to prove that L
_{cd}
cannot be generated
by any parallel communicating grammar system with two regular components only,
no matter the working strategy, but we prove this statement in the grammar
system framework.
