A variant of random context grammars: Semi-conditional grammars
The notion of semi-conditional grammar is introduced. With each rule in the semi-conditional grammar a pair of strings, say \(w_ 1\) and \(w_ 2\), is associated. A rule can be applied to a sentential form w only if \(w_ 1\) is a substring of w and \(w_ 2\) is not contained in it. The paper concentrates mainly to hierarchical properties of families of languages generated by context-free semi-conditional grammars in dependence of the lengths of the \(w_ 1\) and \(w_ 2\) parts of rules. It is proved, that such grammars with very short conditioning parts of rules can generate the whole family of context-sensitive languages. The role of additional regularing mechanisms applied to the case of semi-conditional grammars is studied in connection with the question of generative power of grammars. In the closing section of the article, some interesting open problems are formulated.
inclusions between families of languages
scientific article; zbMATH DE number 3943056