0 votes 0 votes cyk algorithm is used for CFG'S to test which class of problem??? Theory of Computation cyk-algorithm + – Supromit Roy asked Jan 8, 2015 • retagged Nov 28, 2016 by pC Supromit Roy 1.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes CYK algorithm is a dynamic programming method of order O(n^3) to find the membership property of CFG. ansaritk answered Jan 12, 2015 • selected Nov 28, 2016 by pC ansaritk comment Share Follow See all 6 Comments See all 6 6 Comments reply Praveen Saini commented Mar 1, 2015 reply Follow Share Membership property of CFG means, to check whether w ∊ L(G) or not. 2 votes 2 votes rohan mishra commented Jul 24, 2017 reply Follow Share sir, Without using cyk algorithm can we decide whether the string belongs to a given grammar? In exam if it is asked to find membership of a given string it is necessary to use CYK algo? do reply. 0 votes 0 votes Praveen Saini commented Jul 25, 2017 reply Follow Share you can drive the word w from the productions given in Grammar, G using hit and trial. 0 votes 0 votes rohan2018 commented Jul 25, 2017 reply Follow Share Thank you sir. I was confused as the algorithm takes time. If a string is not accepted by hit and trial then it should not be accepted by the algorithm. Is this I conclude. 0 votes 0 votes Praveen Saini commented Jul 25, 2017 reply Follow Share it depends on the length of string and productions given. 0 votes 0 votes rohan2018 commented Jul 25, 2017 reply Follow Share Thank you for your suggestions sir. 1 votes 1 votes Please log in or register to add a comment.