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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIt 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?
On the contrary, it can be arbitrarily hard to decide if a word is in a language. Not only are there undecidable languages (such as the halting language), but there is an infinite hierarchy of undecidable languages, each one even harder than the previous one!
It also seems unlikely that an algorithm for deciding membership in a language would be easily modified to decide if every string in a language has some particular property. That's a completely different problem, requiring completely different analysis.