Publication Details
Controlled Pure Grammar Systems
Zemek Petr, Ing., Ph.D.
formal languages, pure grammar systems, controlled derivations
This paper discusses grammar systems that have only terminals, work in the
leftmost way, and generate their languages under the regulation by control
languages over rule labels. It establishes three results concerning their
generative power. First, without any control languages, these systems are not
even able to generate all context-free languages. Second, with regular control
languages, these systems, having no more than two components, characterize the
family of recursively enumerable languages. Finally, with control languages that
are themselves generated by regular-controlled context-free grammars, these
systems over unary alphabets generate nothing but regular languages. In its
introductory section, the paper gives a motivation for introducing these systems,
and in the concluding section, it formulates several open problems.
@article{BUT96924,
author="Alexandr {Meduna} and Petr {Zemek}",
title="Controlled Pure Grammar Systems",
journal="Journal of Universal Computer Science",
year="2012",
volume="18",
number="14",
pages="2024--2040",
issn="0948-6968",
url="http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems"
}