Remarks on Some Simple Variants of Random Context Grammars
Zsolt Gazdag · Universitätsbibliothek Gießen · 2014
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 random context grammar to achieve computational completeness. We show that every recursively enumerable language can be generated by a random context grammar having restrictions similar to (1) and (2) above and using only one permitting nonterminal symbol.