3 votes 3 votes For every context free grammar (G) there exists an algorithm that passes any $w \in L(G)$ in number of steps proportional to $ln\mid w \mid$ $\mid w \mid$ $\mid w \mid^2$ $\mid w \mid^3$ Theory of Computation ugcnetcse-june2013-paper3 theory-of-computation context-free-grammar + – go_editor asked Jul 17, 2016 recategorized May 30, 2020 by Arjun go_editor 1.9k views answer comment Share Follow See 1 comment See all 1 1 comment reply Verma Ashish commented Oct 22, 2018 reply Follow Share It is CYK algorithm which is applied on Chomsky normal form of CFG. No. of steps required are O(${|w|^3}$) 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes ans is D it is a famous theorem Sanjay Sharma answered Jul 17, 2016 Sanjay Sharma comment Share Follow See all 0 reply Please log in or register to add a comment.