Questions: CYK Algorithm and Membership Testing

Question 1

Why does the CYK algorithm require the grammar to be in Chomsky Normal Form before it can be applied?

• A. CNF grammars generate a strictly larger class of languages than arbitrary CFGs
• B. CNF's restriction to productions A → BC means every substring can be split into exactly two non-empty parts to check — enabling the dynamic programming recurrence
• C. CNF grammars are smaller and reduce the number of table entries needed
• D. CYK only works correctly when the grammar has no epsilon productions

Answer: (B)

The CYK recurrence works because CNF productions are either A → BC (two nonterminals) or A → a (one terminal). The binary structure A → BC is essential: when checking what nonterminals can derive substring s[i..j], you try every split point k and check whether some rule A → BC exists where B derives s[i..k] and C derives s[k+1..j]. This binary decomposition maps cleanly onto the 'two sub-problems' structure of dynamic programming. If productions could have three or more nonterminals, the recurrence would not work in this simple form. Crucially, any CFG can be converted to CNF without changing the language.

Question 2

You have run CYK on a string w of length n against a CNF grammar with start symbol S. What determines whether w is in the language?

• A. Whether any cell in the table contains S
• B. Whether the start symbol S appears in cell T[1,n]
• C. Whether cell T[n,n] contains S after all productions are applied
• D. Whether S appears in every cell along the main diagonal

Answer: (B)

T[1,n] represents the entire string — the set of nonterminals that can derive w[1..n]. The string belongs to the language if and only if the start symbol S can derive the entire string, which means S must appear in T[1,n]. Finding S in any other cell would mean S derives some proper substring of w, not w itself. The cell T[1,n] is the unique cell whose span covers the whole input.

Question 3

CYK is a top-down parsing algorithm: it starts with the start symbol and expands production rules until it either matches the input or exhausts most possibilities.

• T. True
• F. False

Answer: False

CYK is a bottom-up algorithm. It starts by filling the table for individual characters (substrings of length 1), then builds up to substrings of length 2, 3, and so on, until it reaches the full string. At each step, it combines previously computed results for shorter substrings. Top-down parsing (like recursive-descent) starts with the start symbol and tries to expand it to match the input — the opposite direction. CYK's bottom-up approach is what makes the dynamic programming recurrence well-founded: when computing T[i,j], all smaller subproblem cells T[i,k] and T[k+1,j] have already been computed.

Question 4

Converting a CFG to CNF before applying CYK does not change which strings the grammar accepts — the language is preserved.

• T. True
• F. False

Answer: True

CNF conversion uses a series of mechanical transformations (eliminating epsilon productions, unit productions, and rules with more than two nonterminals) that are all language-preserving. The resulting CNF grammar generates exactly the same strings as the original grammar, possibly with the exception of the empty string which requires separate handling. This is why CNF is not a real restriction on CYK's applicability — any CFG can be converted first, and the membership decision will be the same.

Question 5

Where does CYK's O(n³) time complexity come from? Describe the three nested loops and what each iterates over.

Model answer: The three loops are: (1) substring length l, iterating from 1 to n — you must fill cells for every possible substring length before using them; (2) starting position i, iterating from 1 to n−l+1 — you must fill every substring of each length; (3) split point k, iterating from i to i+l−2 — for each cell T[i,j], you try every way to split the substring into two non-empty parts and check all applicable grammar rules. Each loop runs O(n) times, giving O(n³) total cell computations (multiplied by the constant grammar size).

This cubic complexity is unavoidable for general CFGs without additional structure. It makes CYK unsuitable for production parsers handling large inputs, but it remains important as the theoretically optimal algorithm for arbitrary CFGs and as the foundation for probabilistic parsing (where you replace set membership with probability maximization in the same table structure).