Rule-Homogeneous CD Grammar Systems
KOCMAN Radim, KŘIVKA Zbyněk and MEDUNA Alexander. Rule-Homogeneous CD Grammar Systems. AFL 2017. Debrecen, 2017.
CD grammar systems, simulated non-context-free rules
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.
15th International Conference on Automata and Formal Languages, Debrecen, HU