Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 18 / Issue 14

available in:   PDF (154 kB) PS (257 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-018-14-2024


Controlled Pure Grammar Systems

Alexander Meduna (Brno University of Technology, Czech Republic)

Petr Zemek (Brno University of Technology, Czech Republic)

Abstract: 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 regularcontrolled 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.

Keywords: controlled derivations, formal languages, pure grammar systems

Categories: F.1.1, F.4.2, F.4.3