Transformation of leftmost derivations in cooperating distributed grammar systems
type: CreativeWork
description: Cooperating distributed grammar systems allow the generation of non-context-free languages by having multiple context-free grammars derive terminal words in a concurrent way. New transformations of cooperating distributed grammar systems between various leftmost restrictions under the terminal mode of derivation are developed. The results of prior works, in particular concerning the sw-mode and ss-mode of leftmostness, are reviewed and improved upon. There, a critical flaw in the transformation from the ff-mode into the sw-mode is identified and corrected. It is also shown that this transformation is not suitable for use in top-down parsing, as the resulting cooperating distributed grammar systems do not fulfill the LL(k) condition. Further is the transformation from the ss-mode into pushdown automata analyzed for use in transforming into other modes of leftmostness. A possible improvement for transforming from the ss-mode into the ws-mode that requires less additional rules is introduced. This transformation is further expanded upon to transform from the fs-mode into the ws-mode too, establishing a previously unknown relationship between these two modes. The correctness of all transformations introduced is fully proved. Additionally, it is shown that the generative power of the fs and ws-mode is strictly stronger than context-free languages, even for just two components.
abstract: Cooperating distributed grammar systems allow the generation of non-context-free languages by having multiple context-free grammars derive terminal words in a concurrent way. New transformations of cooperating distributed grammar systems between various leftmost restrictions under the terminal mode of derivation are developed. The results of prior works, in particular concerning the sw-mode and ss-mode of leftmostness, are reviewed and improved upon. There, a critical flaw in the transformation from the ff-mode into the sw-mode is identified and corrected. It is also shown that this transformation is not suitable for use in top-down parsing, as the resulting cooperating distributed grammar systems do not fulfill the LL(k) condition. Further is the transformation from the ss-mode into pushdown automata analyzed for use in transforming into other modes of leftmostness. A possible improvement for transforming from the ss-mode into the ws-mode that requires less additional rules is introduced. This transformation is further expanded upon to transform from the fs-mode into the ws-mode too, establishing a previously unknown relationship between these two modes. The correctness of all transformations introduced is fully proved. Additionally, it is shown that the generative power of the fs and ws-mode is strictly stronger than context-free languages, even for just two components.
author: Lindner, Marc Fabian
keywords: grammar systems, leftmost derivations, transformations, terminal derivations, top-down parsing, Grammatiksysteme, Linksableitungen, Transformationen, terminale Ableitungen
date published: 2026-06-08
date modified: 2026-07-24T03:52:15Z
provider: Universität Potsdam - Thes
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Universität Potsdam