On Pushdown CD-Systems of Regular Grammars

Abstract

It is known and straightforward to show that cooperative distributed (CD) systems of regular grammars can generate only regular languages independently of the mode of cooperation (e.g., ?,t,?k,=k,?k for k?N, k>0). In this paper CD-systems of regular grammars are shown such that the next active component is chosen by the help of an external pushdown storage. We show that these systems can generate exactly the context-free languages. Moreover, based on this fact, a strong relation to fractal automata is given. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.