CYK Algorithm for CFLs

1. The Membership Problem and Its Challenges

The membership problem for CFLs is formally stated as:
Given a Context-Free Grammar (CFG) $G$ and a string $w$, is $w\in L(G)$?

A naive approach would be to start generating all possible strings from the grammar's start symbol. However, if the language is infinite, this process may never terminate, so it isn't a viable algorithm.

A more refined approach, which we've touched on before, relies on converting the grammar to Chomsky Normal Form (CNF). A key property of a CNF grammar is that any derivation of a string of length $n>0$ requires exactly $2n-1$ steps. This guarantees that we can limit our search, making the problem decidable. However, trying to check all possible derivations of that length can lead to an exponential number of possibilities, which is highly inefficient.

This is where dynamic programming comes in, providing a polynomial-time solution.

2. The Core Idea: Dynamic Programming

The CYK algorithm solves the membership problem by breaking it down into smaller, manageable subproblems. Instead of asking "Can the start symbol $S$ generate the whole string $w$?" from the top down, it asks from the bottom up: "Which variables can generate the various substrings of $w$?"

The algorithm builds a table that stores the solutions to these subproblems. For a string $w=w_1{w}_2...w_n$, we'll construct an $n\times n$ table, let's call it $T$, where the entry $T_{i,j}$ will contain the set of all variables that can generate the substring starting at position $i$ of length $j$.

To get a clear, high-level overview of this dynamic programming strategy, please watch the following video. It explains why a grammar in CNF is crucial and how the problem of generating a string can be recursively divided into generating its constituent parts.

As the video explains, the key insight is that for a rule $A\to BC$ in CNF, if $A$ generates a substring $s$, then $s$ must be splittable into two non-empty parts, $s_1$ and $s_2$, such that $B$ generates $s_1$ and $C$ generates $s_2$. The CYK algorithm systematically checks all possible splits for all substrings.

3. The CYK Algorithm: A Step-by-Step Guide

Let's formalize the algorithm. Given a CFG $G$ in CNF and an input string $w=w_1{w}_2...w_n$ of length $n$.

1. Initialization (Substrings of length 1):
   For each character $w_i$ in the string, find all variables $A$ that have a rule $A\to w_i$. Fill the first row of our table, $T_{i,1}$, with these variables. This represents all variables that can generate substrings of length 1.

2. Iterative Step (Substrings of length $j>1$):
   For each substring length $j$ from 2 to $n$:
   For each starting position $i$ from 1 to $n-j+1$:

   • We want to compute $T_{i,j}$, which corresponds to the substring $w[i..i+j-1]$.
   • We consider every possible split point $k$ for this substring (where $1\le k<j$). Each split divides the substring into two smaller parts:
     • Part 1: w[i..i+k-1] (of length k)
     • Part 2: w[i+k..i+j-1] (of length j-k)
   • The variables that can generate these smaller parts have already been computed and are stored in $T_{i,k}$ and $T_{i+k,j-k}$.
   • We then check every rule of the form $A\to BC$. If $B\in T_{i,k}$ and $C\in T_{i+k,j-k}$, it means $A$ can generate the full substring w[i..i+j-1]. We add $A$ to the set in $T_{i,j}$.

3. Conclusion:
   After filling the entire table, we check the top-most cell, $T_{1,n}$. If the start symbol $S$ is in this set, it means $S$ can generate the entire string $w$. The string is a member of the language. Otherwise, it is not.

A Worked Example

The process of filling the table is best understood with a concrete example. The following video provides an excellent, clear walkthrough.

The table structure in the video is an upper-triangular matrix, where cell $(i,j)$ holds variables for the substring $w_i\dots w_j$. This is a common and intuitive way to visualize the algorithm.

4. Formal Algorithm and Complexity

For a more rigorous look at the algorithm, including its formal pseudocode and another detailed example, the following lecture notes are an excellent resource.

As detailed in the notes, the CYK algorithm has three nested loops:

1. Looping over the substring length, $l$ (from 2 to $n$).
2. Looping over the start position, $i$ (from 1 to $n-l+1$).
3. Looping over the split point, $k$ (from $i$ to $j-1$).

This structure leads to a time complexity of $O(n^3\cdot |G|)$, where $n$ is the length of the string and $|G|$ is the size of the grammar (number of rules). Since the grammar is fixed for a given language, the complexity is typically stated as $O(n^3)$. This polynomial-time performance is a significant improvement over exponential methods and proves that every context-free language is in the complexity class P.

Conclusion

In this lesson, we tackled the fundamental membership problem for CFLs and learned a powerful and efficient algorithm to solve it.

Key Takeaways:

• The membership problem for a CFL—deciding if a string $w$ is in $L(G)$—is decidable.
• The CYK algorithm provides an efficient, polynomial-time solution using dynamic programming.
• A prerequisite for the algorithm is that the grammar must be in Chomsky Normal Form (CNF).
• The algorithm works by systematically building a table of which variables can generate which substrings of the input string, from length 1 up to $n$.
• A string is in the language if and only if the start symbol $S$ is in the table cell corresponding to the entire string.
• The $O(n^3)$ complexity of the CYK algorithm proves that all CFLs are in the complexity class P.

Preview of the Next Lesson:
The CYK algorithm is one of several important "decision properties" for CFLs. Having answered the membership question, we will next explore algorithms to answer other fundamental questions: Is a given CFL empty? Is it finite or infinite? These problems also have algorithmic solutions that rely on analyzing the structure of the grammar itself.