Publication Details
One-Sided Random Context Grammars
Zemek Petr, Ing., Ph.D.
Regulated rewriting, random context grammars, one-sided variants, generative
power, language families
The notion of a one-sided random context grammar is defined as
a context-free-based regulated grammar, in which a set of permitting symbols and
a set of forbidding symbols are attached to every rule, and its set of rules is
divided into the set of left random context rules and the set of right random
context rules. A left random context rule can rewrite a nonterminal if each of
its permitting symbols occurs to the left of the rewritten symbol in the current
sentential form while each of its forbidding symbols does not occur there.
A right random context rule is applied analogically except that the symbols are
examined to the right of the rewritten symbol.
The paper demonstrates that without erasing rules, one-sided random context
grammars characterize the family of context-sensitive languages, and with erasing
rules, these grammars characterize the family of recursively enumerable
languages. In fact, these characterization results hold even if the set of left
random context rules coincides with the set of right random context rules.
Several special cases of these grammars are considered, and their generative
power is established. In its conclusion, some important open problems are
suggested to study in the future.
@article{BUT49880,
author="Alexandr {Meduna} and Petr {Zemek}",
title="One-Sided Random Context Grammars",
journal="Acta Informatica",
year="2011",
volume="48",
number="3",
pages="149--163",
doi="10.1007/s00236-011-0134-y",
issn="0001-5903",
url="http://www.springerlink.com/content/c70163w7764u8660/"
}