KOCMAN Radim, KŘIVKA Zbyněk and MEDUNA Alexander. Rule-Homogeneous CD Grammar Systems. AFL 2017. Debrecen, 2017.
Publication language:english
Original title:Rule-Homogeneous CD Grammar Systems
Book:AFL 2017
Conference:15th International Conference on Automata and Formal Languages
Place:Debrecen, HU
+Type Name Title Size Last modified
iconrhcdgs-short.pdf132 KB2017-09-11 16:04:45
^ Select all
With selected:
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.

Your IPv4 address: