View article

It is known that the expressive power of random context grammars is the same with or without the following restrictions: (1) in every rule either the permitting set or the forbidding set is empty and the other one is a singleton and (2) each rule that rewrites the same nonterminal symbol have the same permitting and forbidding sets. It is also known that the permitting variants of these restricted random context grammars are equivalent to permitting random context grammars. In this paper we show a similar result concerning the forbidding case. We show that, when erasing rules are allowed, the forbidding variants of these restricted random context grammars are equivalent to forbidding random context grammars.

It is also known that forbidding random context grammars are weaker than the computationally complete random context grammars. Thus, it is natural to ask how many permitting symbols are required in a …