Transformation of leftmost derivations in cooperating distributed grammar systems

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.

Level thesis:degree_level

master

Grantor dc:publisher

Universität Potsdam

Year

2026

Author dc:creator

• Lindner, Marc Fabian

Contributors dc:contributor

• Bordihn, Henning
• Frank, Mario

• grammar systems
• leftmost derivations
• transformations
• terminal derivations
• top-down parsing
• Grammatiksysteme
• Linksableitungen
• Transformationen
• terminale Ableitungen

Statement dc:rights

• CC-BY - Namensnennung 4.0 International

Repository record source_url

https://publishup.uni-potsdam.de/frontdoor/index/index/docId/70408

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-potsdam:70408