Publication Details

Rule-Homogeneous CD Grammar Systems

KOCMAN Radim, KŘIVKA Zbyněk and MEDUNA Alexander. Rule-Homogeneous CD Grammar Systems. AFL 2017. Debrecen, 2017.
Type
abstract
Language
english
Authors
Keywords

CD grammar systems, simulated non-context-free rules

Abstract

A homogeneous rule has its left-hand side formed by a string of identical symbols. Consider two-component CD grammar systems that work under the * mode or the t mode. This study presents two transformations that turn arbitrary grammars into equivalent two-component CD grammar systems with a context-free component and a homogeneous component. From one transformation, the homogeneous component results with two rules of the form 11 -> 00 and 0000 -> 2222, while the other transformation produces the homogeneous component with two rules of the form 11 -> 00 and 0000 -> eps. Apart from this significant restriction of non-context-free rules, the study describes several other useful properties concerning these systems and the way they work.

Published
2017
Pages
3
Book
AFL 2017
Conference
15th International Conference on Automata and Formal Languages, Debrecen, HU
Place
Debrecen, HU
Files
Back to top