Abstract
In this paper, we address several open problems concerning pure grammar systems (pGSs) and their controlled versions. More specifically, we prove the following four results. (I) Regular-controlled pGSs having a single component define the family of regular languages. (II) pGSs having two components controlled by infinite regular languages define the family of recursively enumerable languages. (III) Regular-controlled pGSs without any erasing rules define the family of regular languages not containing the empty string. (IV) pGSs define a proper subfamily of the family of regular languages.
Acknowledgements
This work was supported by the following grants: BUT FIT-S-11-2, MŠMT ED1.1.00/02.0070, TAČR TE01010415, and CEZ MŠMT MSM0021630528. The authors thank both anonymous referees for useful comments regarding the first version of this paper.