One-sided random context grammars with a limited number of right random context rules (Q385971)

A one-sided random context grammar represents a variant of a random context grammar. In this variant, 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. These grammars can generate every recursively enumerable language. In this paper, it is proven that any recursively enumerable language can be generated by a one-sided random context grammer having no more than two right random context rules.