On Descriptions of Context-Free Languages by CD Grammar Systems

In this paper, the problem is revisited to what degree cooperating distributed (CD) grammar systems are more succinct than context-free grammars when describing context-free languages. The measures of descriptional complexity which are mainly considered are the number of variables and the number of productions. Some open problems stated in the literature are solved. It is proved that CD grammar systems can reach the best possible increase of efficiency compared with context-free grammars in all standard derivation modes with respect to both measures. In contrast to preliminary papers, only languages over unary or binary alphabets are used in the proofs, and the number of components in the CD grammar systems is bounded by a constant. Finally, it is shown that the best possible result can generally not be achieved for a different measure, the total number of symbols.