The primary function of the CYK algorithm is to solve the membership problem for Context-Free Languages: Given a Context-Free Grammar G (in CNF) and an input string w, determine efficiently whether w is a valid string belonging to the language L(G). If the string is valid, the algorithm can also be extended to reconstruct one or all possible parse trees for the string.

The CYK algorithm constructs a triangular table (or matrix), often denoted as P or T, of size n times n, where n is the length of the input string w. Each cell T[i][j] (or P[i,j]) in this table will store a set of non-terminal symbols from the grammar. Specifically, T[i][j] will contain all non-terminals A such that the substring of w starting at index i and having length j (i.e., w_iw_i+1dotsw_i+j−1) can be derived from A. The algorithm fills this table in a bottom-up fashion: it first considers all substrings of length 1, then length 2, and so on, until it processes the entire string.

This step fills the first 'row' of the triangular table, corresponding to substrings of length 1 (individual characters). For each character w_i in the input string (from i=1 to n): Set T[i,1] to be the set of all non-terminals A in the grammar such that there is a production rule Ato w_i. This is the direct terminal derivation step from CNF rule type Atoa.

This is the main dynamic programming loop, where the algorithm builds up solutions for longer substrings based on solutions for shorter substrings. For each substring length j from 2 to n: For each starting position i from 1 to (n−j+1): (This iterates through all substrings of length j) Initialize T[i,j] as an empty set. For each possible split point k within the current substring (from 1 to j−1): Retrieve the sets of non-terminals that can generate these two parts from the already computed table cells...

After the table is completely filled, the algorithm checks the top-most cell: T[1,n]. This cell corresponds to the entire input string w. The string w is in the language L(G) if and only if the start symbol S is present in the set T[1,n].

Time Complexity: The algorithm has a time complexity of O(n3∣G∣), where n is the length of the input string and ∣G∣ is the size of the grammar (roughly, the number of production rules). The three nested loops (for j, i, and k) contribute the n3 factor. The lookup and set operations depend on grammar size. Space Complexity: The algorithm requires O(n2) space to store the triangular table.

Generality: It works for any Context-Free Grammar, provided it is first converted to CNF. It does not require any special properties like LL(k) or LR(k) grammars needed by other parsing algorithms. Handles Ambiguity: If a grammar is ambiguous (meaning a string can have multiple parse trees), CYK can find all possible derivations (though the basic algorithm only checks for membership). Simplicity of Implementation: While O(n3) is slower than linear-time parsers, its dynamic programming structure makes it relatively straightforward to implement correctly.

Let's use a simple grammar G=(S,A,B,a,b,P,S) in CNF:
P:
1. S → AB
2. A → a
3. B → b
Let the input string be w=‘ab‘. Length n=2. Table T (size 2×2): Initialize with empty sets: T[1,1]=emptyset, T[2,1]=emptyset T[1,2]=emptyset Step 1: Length 1 Substrings (j=1) ● T[1,1] (for substring w_1=‘a‘):
○ Check rules X → ‘a‘. Rule 2: A → ‘a‘.
○ So, T[1,1]=A. ● T[2,1] (for substring w_2=‘b‘):
○ Check rules X → ‘b‘. Rule 3: B → ‘b‘.
○ So, T[2,1]=B. Step 2: Length 2 Substrings (j=2) ● T[1,2] (for substring w_1w_2=‘ab‘):
○ Only one possible split point: k=1. (Splits into w_1 and w_2)
■ First part: w_1=‘a‘. Non-terminals from T[1,1]=A.
■ Second part: w_2=‘b‘. Non-terminals from T[2,1]=B.
■ Consider pairs (P,Q) where P in T[1,1] and Q in T[2,1]. Only pair is (A,B).
■ Check grammar rules: Is there a rule X → AB? Yes, Rule 1: S → AB.
■ Add S to T[1,2].
○ So, T[1,2]=S.
Acceptance Check:
Is the start symbol S in T[1,2]? Yes, S in S. Therefore, the string ab is accepted by the grammar.