Publication Details

Controlled Pure Grammar Systems

MEDUNA Alexander and ZEMEK Petr. Controlled Pure Grammar Systems. Journal of Universal Computer Science, vol. 18, no. 14, 2012, pp. 2024-2040. ISSN 0948-6968. Available from: http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems
Czech title
Řízené čisté gramatické systémy
Type
journal article
Language
english
Authors
URL
Keywords

formal languages, pure grammar systems, controlled derivations

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 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.

Published
2012
Pages
2024-2040
Journal
Journal of Universal Computer Science, vol. 18, no. 14, ISSN 0948-6968
Publisher
Springer Verlag
UT WoS
000310430600007
EID Scopus
BibTeX
@ARTICLE{FITPUB9857,
   author = "Alexander Meduna and Petr Zemek",
   title = "Controlled Pure Grammar Systems",
   pages = "2024--2040",
   journal = "Journal of Universal Computer Science",
   volume = 18,
   number = 14,
   year = 2012,
   ISSN = "0948-6968",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9857"
}
Back to top