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, \le k,=k, \ge k\) for \(k\in \mathbb 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Pushdown CD-Systems of Regular Grammars

  • Benedek Nagy

摘要

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, \le k,=k, \ge k\) for \(k\in \mathbb 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.