Remarks on context-free parallel communicating grammar systems generating crossed agreements
Parallel communicating grammar systems are language generating devices consisting of several grammars which derive synchronously their sentential forms and communicate with each other by sending their sentential forms to another component on request. Due to collaboration, grammar systems with context-free components are more powerful than a single context-free grammar; they even can generate all recursively enumerable languages. In natural languages, there occur constructions that cannot be modelled by context-free languages. Three important phenomena are the so-called multiple agreements, crossed agreements and replication which are represented by the three non-context-free languages K-1 = {a(n)b(n)c(n) vertical bar n >= 1}, K-2 = {a(n) b(m)c(n)d(m) vertical bar m >= l, n >= 1}, and K-3 = {ww vertical bar w is an element of {a, b}(+)}, respectively. In the present paper, we give parallel communicating grammar systems ( PC grammar systems) that are context-free and that generate the language K-2, working in different modes. In two cases, the results are optimal.
parallel communicating grammar systems crossed agreements number of components