A predicate for separating language classes.
Henning Fernau · 1995
: We show how a predicate can be used to separate language classes in a remarkably concise way, e.g., L(P,CF\\Gamma) and L(P,CF\\Gamma,ut). It has been a long-standing open problem whether appearance checking enhances the power of programmed grammars or not. By now, two independent complicated proofs appeared for the separation result in question [4, 3]. In this note, we present another decidability argument which readily implies the abovementioned result and is also applicable to other situations. Let h : \\Sigma ! \\Delta be an arbitrary homomorphism, R ` \\Sigma be a regular language, and L ` \\Sigma be a language from some language class L. Consider the predicate P h;R;L on \\Delta defined by P h;R;L (w) () w 2 h(R " L): If L is a subfamily of a language class comprising only of recursive languages which is closed under arbitrary homomorphisms and intersection with regular sets, then the above predicate is decidable for L, i.e., for every h, R, and L 2 L, there is an alg...