Left-forbidding cooperating distributed grammar systems |
| |
Authors: | Filip Goldefus Tomá? Masopust Alexander Meduna |
| |
Affiliation: | 1. Faculty of Information Technology, Brno University of Technology, Bo?etěchova 2, Brno 61266, Czech Republic;2. Institute of Mathematics, Czech Academy of Sciences, ?i?kova 22, 616 62 Brno, Czech Republic |
| |
Abstract: | A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|