A shrinking lemma for random forbidding context languages

Random context grammars belong to the class of context-free grammars with r egulated rewriting. Their productions depend on context that may he randoml y distributed in a sentential form. Context is classified as either permitt ing or forbidding, where permitting context enables the application of a pr oduction and forbidding context inhibits it. We concentrate on non-erasing grammars that use forbidding context only. We show that they are strictly w eaker than the non-erasing random context grammars and prove a shrinking le mma for their languages. (C) 2000 Elsevier Science B.V. All rights reserved .