1 votes 1 votes If the parse tree of a word w generated by a Chomsky form grammar has no path of length greater than i, then the word w is of length no greater than $2^{i+1}$ no greater than $2^i$ no greater than $2^{i-1}$ no greater than $i$ Compiler Design chomsky-normal-form ugcnetcse-dec2012-paper3 parsing + – Sanjay Sharma asked Apr 28, 2016 recategorized Jun 23, 2022 by Arjun Sanjay Sharma 3.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes Answer C If a parse tree for a word string w is generated by a CNF and the parse tree has a path length of at most i, then the length of w is at most 2i-1 refer: http://textofvideo.nptel.iitm.ac.in/106106049/lec16.pdf omveer answered Sep 6, 2016 selected Sep 19, 2016 by Sankaranarayanan P.N omveer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Option b is correct . You can see this :) It is proved my Induction and recurrence relation http://nptel.ac.in/courses/106106049/downloads/Properties%20of%20CFL.pdf Dexter answered Apr 28, 2016 Dexter comment Share Follow See all 0 reply Please log in or register to add a comment.