CYK Algorithm
Given the grammar in CNF:
S → AB | BC
A → BA | a
B → CC | b
C → AB | a
What is the first row of the CYK table for the input string 'baaba'?
In the CYK algorithm, when filling cell (2,1) for the string 'baaba', which pairs of cells do we need to check?
What is the final cell we need to check to determine if 'baaba' is accepted by the grammar?
If cell (3,1) contains {A, B} and cell (2,4) contains {C}, what does this tell us about the substring 'baa'?
What is the maximum number of non-terminals that can be in any cell of the CYK table?
If a grammar has 5 non-terminals and the input string is of length 4, what is the size of the CYK table?
What is the minimum number of steps required to fill the CYK table for a string of length n?
If a grammar has a production rule A → BC and we find that B can generate a substring of length 2 and C can generate a substring of length 3, what can we conclude?
What is the relationship between the CYK algorithm and dynamic programming?