0 votes 0 votes If a parse tree is made for a w ε L(G), when G is in Chomsky-Normal form then what would be it's least height?? Plz explain what and how... Theory of Computation made-easy-test-series theory-of-computation grammar + – ARUN KUMAR 3 asked Oct 12, 2016 • edited Mar 4, 2019 by akash.dinkar12 ARUN KUMAR 3 547 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes CNF can be represented as a binary tree. Consider worst case that is full binary tree. In this case |w| <= 2h-1 Now take log both sides log2|w| <= h-1 h >= log2|w| + 1 Digvijaysingh Gautam answered Oct 12, 2016 Digvijaysingh Gautam comment Share Follow See all 0 reply Please log in or register to add a comment.
