# What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?

So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK?

is it being used anywhere?

If I'm not mistaken(correct me If I'm wrong) the benefit of CYK is that since we can convert any CFG to CNF form therefore i guess we can apply this to non deterministic CFG's and also Inherently ambiguous grammars which are CFG

but are these really benefits? i mean whats the usage of using membership algorithm for Inherently ambiguous CFG's or non deterministic CFG's? where would we use a Inherently ambiguous CFG or non deterministic CFG ?!

Isn't the main usage of membership for compilers? which they already use LR algorithms?

• Answered on quora: quora.com/What-is-CYK-algorithm-used-for-practically. – Yuval Filmus Apr 14 '18 at 19:14
• You assume that the algorithm has (to have) practical relevance. Why? – Raphael Apr 15 '18 at 8:20
• Inherently ambiguous grammars: Only Languages can be Inherently ambiguous, while their grammars are always nondeterministic. – user Jul 6 '19 at 22:22