Publication Details

Left Random Context ET0L Grammars

MEDUNA, A.; ZEMEK, P. Left Random Context ET0L Grammars. Fundamenta Informaticae, 2013, vol. 123, no. 3, p. 289-304. ISSN: 0169-2968.
Czech title
Levé ET0L gramatiky s nahodilým kontextem
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Zemek Petr, Ing., Ph.D.
URL
Keywords

Regulated rewriting; ET0L grammars; random context; left variants; generative
power; language families

Abstract

Consider ET0L grammars. Modify them such that a set of permitting symbols and
a set of forbidding symbols are attached to each of their rules, just like in
random context grammars. A rule like this can rewrite a symbol if each of its
permitting symbols occurs to the left of the symbol to be rewritten in the
current sentential form while each of its forbidding symbols does not occur
there. ET0L grammars modified in this way are referred to as left random context
ET0L grammars, and they represent the principal subject of the investigation in
this paper.

We prove that these grammars characterize the family of recursively enumerable
languages, and without erasing rules, they characterize the family of
context-sensitive languages. We also introduce a variety of special cases of
these grammars and establish their generative power. In the conclusion, we put
all the achieved results into the context of formal language theory as a whole
and formulate several open questions.

Published
2013
Pages
289–304
Journal
Fundamenta Informaticae, vol. 123, no. 3, ISSN 0169-2968
DOI
10.3233/FI-2013-811
BibTeX 
@article{BUT103402,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Left Random Context ET0L Grammars",
  journal="Fundamenta Informaticae",
  year="2013",
  volume="123",
  number="3",
  pages="289--304",
  doi="10.3233/FI-2013-811",
  issn="0169-2968",
  url="http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2"
}
Back to top