Chomsky normal form is critical to the CKY algorithm.
Deriving substrings of length 1, A _* xp1, is determined by a simple scan of the terminating productions.
Deriving longer substrings, A _* xpq where q 2, requires A _ BC _* xpq , and then B derives a string of length k, 1 k < q, and C derives the remainder, a string of length q-k that is, B _* xpk and C _* xp+k,qk.
Therefore the non-terminals deriving the substrings of length 2 are determined by knowing those that derive substrings of length 1, those deriving substrings of length 3 are known from those deriving lengths 1 and 2, etc.
Previous slide | Next slide | Back to first slide | View graphic version |