In this section, we will discuss the CYKS¹ algorithm. This algorithm, which relies on a context-free grammar \(G\) being in Chomsky normal form (See the previous section), determines whether 1. A string \(w\) belongs to the language generated by the grammar and 2. Derives all the parse trees that yield that string.

Intuitions behind the algorithm

In this first video, I give you the general intuitions about the CYKS algorithm by first presenting the recursive nature of the algorithm and then by looking at an example where I build the parse tree bottom-up. Note that this is only an intuitive presentation of the algorithm since, in general, in requires the construction of a dynamic programming table. We will look at that in the following sub-section.

Running the CYKS algorithm

In this video, I run the CYKS algorithm on the following grammar G which has already by converted to CNF. To do so, I present the CYKS algorithm in a slightly more formal way, discussing its dynamic programming table. This recording comes from an in-person tutorial that I gave in Fall 2025. The video starts at the right place for your convenience.

Exercises

Exercise. Convert the following grammar G to CNF and run the CYKS algorithm on G using w = aaa.

Grammar G:
    S -> aAa | bBb | epsilon
    A -> C | a
    B -> C | b
    C -> CDE | epsilon
    D -> A | B | ab