A variant of random context grammars: Semi-conditional grammars

AbstractA semi-conditional grammar is a context-free grammar whose rules have two associated strings, w1, w2, and such a rule can be applied to a sentential form w only when w1 is a substring of w but w2 is not a substring of w. The paper investigates the generative capacity of such grammars. It is proved that semi-conditional grammars with very short conditions w1, w2 characterize the context-sensitive languages (recursively enumerable languages when λ-rules are allowed). Moreover, when a further restriction in derivation is added (leftmost derivation, ordered, programmed, matrix or regular control restrictions), then also semi-conditional grammars with only forbidding conditions (w1 missing) or with only permitting conditions (w2 missing) again characterize the context-sensitive languages (recursively enumerable, when λ-rules are used)