Given a context-free grammar G = (V, _, P, S) in Chomsky normal form, and a candidate string x = _1_2 … _n, where__i__ (1ŠiŠn), the CKY algorithm tests the membership of x_L(G).
The strategy is based on certain sets of non-terminals. Namely, Vpq = (A_V| A _* xpq}, where xpq = _p_p+1 … _p+q-1 (i.e., the substring of x of length qstarting at _p), for each p and q, 1 Š p Š n and 1 Š q Š n-p+1.
If these sets of non-terminals are known, then x_L(G) if and only if S_V1n so this provides an algorithm.
Previous slide | Next slide | Back to first slide | View graphic version |