It isn't very hard to decide if word belongs to language L. CYK algorithm should do here.Occured thought, can CYK be modified to detect if all words of language L contain some specific subword?
Decidability algorithm, whether substring belongs to L
context free;decision problem