Detail publikačního výsledku

Controlled Pure Grammar Systems

MEDUNA, A.; ZEMEK, P.

Original Title

Controlled Pure Grammar Systems

English Title

Controlled Pure Grammar Systems

Type

WoS Article

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

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

Keywords

formal languages, pure grammar systems, controlled derivations

Key words in English

formal languages, pure grammar systems, controlled derivations

Authors

MEDUNA, A.; ZEMEK, P.

RIV year

2013

Released

28.10.2012

ISBN

0948-6968

Periodical

JOURNAL OF UNIVERSAL COMPUTER SCIENCE

Volume

18

Number

14

State

Republic of Austria

Pages from

2024

Pages to

2040

Pages count

17

URL

http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems

Full text in the Digital Library

http://hdl.handle.net/

BibTex

@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-695X",
  url="http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems"
}