Solutions to four open problems concerning controlled pure grammar systems

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.

Keywords:

• formal languages
• pure grammar systems
• controlled leftmost derivations
• regular languages
• erasing rules

2010 AMS Classifications:

• 68Q01
• 68Q05
• 68Q42
• 68Q45
• 68R01

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.