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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
answered Nov 20 '16 at 14:20
