0 votes 0 votes For any context-free grammar there is a parser that takes at most O (n$^3$ ) time to parse a string of n terminals. True or False? Compiler Design compiler-design context-free-grammar parsing true-false + – Reshu $ingh asked Feb 9, 2019 • retagged Jun 22, 2022 by Lakshman Bhaiya Reshu $ingh 913 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Shaik Masthan commented Feb 9, 2019 reply Follow Share using CYK algorithm we will test the membership problem of CFG. So, given statement is true ! 2 votes 2 votes Reshu $ingh commented Feb 9, 2019 reply Follow Share I have 1st time heard about CYK Algo. Can you please elaborate @Shaik Masthan 0 votes 0 votes Shashi Shekhar 1 commented Feb 9, 2019 reply Follow Share In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars. It employs bottom-up parsing and dynamic programming. It is used to decide whether a given string belongs to a language of grammar or not. CYK Algorithm operates only on context free grammars given in Chomsky Normal Form (CNF). 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Yes , it is true , for CFG in Chomsky Normal form , to parse a string it takes O(n^3) time . Shashi Shekhar 1 answered Feb 9, 2019 Shashi Shekhar 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply Reshu $ingh commented Feb 9, 2019 reply Follow Share Any valid reason? 0 votes 0 votes Shashi Shekhar 1 commented Feb 9, 2019 reply Follow Share It's because CYK ALGO takes that much time in worst case , here is the link for proof of O(N^3) time complexity: https://math.stackexchange.com/questions/255089/how-to-prove-cyk-algorithm-has-on3-running-time 1 votes 1 votes Please log in or register to add a comment.
