A variant of random context grammars: Semi-conditional grammars (Q1072714)

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.