CKY Algorithm Explained: Parsing with Chomsky Normal Form

Constituency parsing is the task of assigning a hierarchical syntactic structure to a sentence, breaking it down into constituents (words or phrases functioning as units) using a parse tree. The CKY algorithm, a dynamic programming approach, finds the most likely parse tree for a given sentence by applying probabilistic context-free grammars (PCFGs). PCFGs extend context-free grammars by associating each production rule with a probability, estimated from annotated treebank data. The algorithm works by initializing a table where each cell represents a substring, then filling it bottom-up by considering all possible split points and combining probabilities of compatible rules. This approach resolves syntactic ambiguities by selecting the highest-probability parse tree, which is essential for downstream NLP tasks like machine translation, semantic role labeling, and grammar checking.

Tree banks are collections of training data consisting of sentences paired with their underlying parse trees, annotated by hand by linguists. The Penn Wall Street Journal Tree Bank contains approximately 50,000 sentences (1 million words) of such annotated data. Parse trees represent hierarchical structure through multiple levels: the first level encodes part-of-speech tags for each word, while higher levels show hierarchical grouping of words into constituents. Constituents are phrases identified by nodes that dominate sequences of words, such as NP (noun phrase) dominating 'the burglar' or VP (verb phrase) dominating 'robbed the apartment.' This hierarchical organization reveals the grammatical architecture of sentences.

A parse tree (or concrete syntax tree) is an ordered, rooted tree that represents the syntactic structure of a string according to a context-free grammar, with two main types: constituency-based parse trees that distinguish between terminal and non-terminal nodes (where interior nodes represent grammatical categories like S, NP, VP, V, D, N and leaves represent lexical tokens), and dependency-based parse trees that treat all nodes as terminal; these trees help analyze sentence structure by showing hierarchical relationships between words and phrases, with constituency trees providing more detailed syntactic information through phrasal categories while dependency trees offer a simpler structure with fewer nodes.

This section explains constituency parsing, which breaks sentences into hierarchical phrases and clauses represented as trees. The approach uses Context-Free Grammar (CFG) with production rules defining how structures assemble and a lexicon providing terminal symbols. Rules like S→NP VP specify valid sentence structures. Parsing yields different trees for ambiguous sentences, reflecting human linguistic ambiguity. For example, 'She enrolled in the course at the university' can parse as either enrolling at the university or enrolling in a university course. This demonstrates that parsers reflect underlying algorithmic biases and that natural language inherently contains structural ambiguity requiring careful interpretation.

Constituency parsing represents sentences as tree structures where words group into constituents like noun phrases, verb phrases, and prepositional phrases. These structures correspond to context-free grammar representations in computer science, providing a powerful prior for understanding language structure and disambiguating sentences with ambiguous attachments. Tree RNNs, CNNs, and RNNs represent fundamentally different approaches to language modeling with distinct trade-offs. Tree RNNs compute representations only for grammatically valid phrases identified by parsing, providing linguistically plausible representations but requiring parsing infrastructure. CNNs compute representations for every possible word combination regardless of grammatical validity, offering computational simplicity but potentially capturing less cognitively plausible representations. RNNs process sequences linearly from left to right, making them computationally efficient but unable to represent hierarchical structure. Tree RNNs offer a middle ground, capturing hierarchical structure while still being amenable to gradient-based learning through backpropagation through structure.

A key challenge in dynamic programming is overlapping subproblems—when solving sub-problems recursively, the same sub-problem may be solved multiple times. For example, computing Fibonacci numbers involves computing F(2) twice when calculating F(5). To avoid redundant computation, dynamic programming stores solutions to solved sub-problems. There are three basic methods: recursion with memoization (top-down), and bottom-up with tabulation. This optimization dramatically improves efficiency for problems with many overlapping sub-problems.

A problem is suitable for dynamic programming if it exhibits overlapping subproblems. This means that the recursive solution repeatedly solves the same subproblems multiple times. When solving a large problem, we break it into smaller subproblems, and if those subproblems themselves break down into identical smaller sub-subproblems, we can save computation time by storing and reusing their solutions. This overlapping nature is one of the two key conditions (along with optimal substructure) that indicates DP is applicable.

The Overlapping Subproblems property is a key characteristic of problems suitable for Dynamic Programming, where the same subproblems are solved multiple times during the recursive computation. This redundancy causes exponential time complexity in naive recursive approaches, as demonstrated by the Fibonacci sequence calculation. To optimize such problems, we can use techniques like memoization (storing results of solved subproblems) or tabulation (precomputing solutions in a table) to avoid redundant computations and achieve polynomial time complexity.

A recursive solution contains many repeated subproblems. For LCS, while the recursion tree has exponential size (2^(m+n)), there are only m×n distinct subproblems (each characterized by i and j indices). This is because each subproblem corresponds to a unique pair of prefix lengths. The small number of distinct subproblems compared to the total number of recursive calls makes memoization effective.

Overlapping subproblems occur when a recursive function makes two or more recursive calls. If only one recursive call is made from one call to another, there will never be overlapping. However, when two or more calls are made, there's a possibility that the same subproblem (black node) has already been solved before. This allows us to store the result and reuse it later, which is the essence of Dynamic Programming optimization.

A grammar is a formal system consisting of variables, terminals, production rules, and a start variable that generates strings in a language by replacing variables with combinations of variables and terminals according to specified rules, ultimately producing strings containing only terminals; unlike DFAs/NFAs which recognize whether a string belongs to a language, grammars provide a mechanism to actually generate example strings from a language.

A formal language is a set of strings, where strings are sequences of symbols from an input alphabet. Languages can be studied through two complementary approaches: grammars (generating devices) and machines (accepting devices). Finite automata recognize languages using states, transitions, an initial state, and final states. A string belongs to a language if the machine reaches a final state when processing it. Grammars consist of start symbols, non-terminals, terminals, and production rules that generate strings. Both grammars and automata are essential for understanding formal languages, with grammars generating strings and automata recognizing them. Regular languages represent the simplest class of formal languages, generated by regular grammars and recognized by finite automata.

A formal grammar consists of four components: variables (non-terminals represented by capital letters), terminals (represented by lowercase letters), a starting symbol (typically 'S'), and a set of production rules. A language is the set of all strings that can be generated by applying these production rules starting from the starting symbol. The instructor demonstrates how different grammars generate different languages, including examples like generating strings with equal numbers of 'a's and 'b's (a^n b^n), strings with more 'a's than 'b's (a^+ b), and strings containing only 'a's (a^+). The language generated depends on the production rules and how variables are recursively replaced with terminals.

A language is a collection of strings over an alphabet following grammar rules. Grammar provides format specifications while meaning is irrelevant. For alphabet {0, 1}, a language might include all strings starting with '1' (11, 110, 111, 1100). Natural languages prioritize meaning; formal languages prioritize format. This distinction is fundamental to automata theory and computation.

In Theory of Computation, grammar is a formal system for representing languages through structured rules. A grammar G is defined as a quadruple (V, T, P, S): V is the set of variables (non-terminal symbols, capital letters), T is the set of terminals (basic building blocks, small letters), P is the set of production rules specifying replacements, and S is the start symbol initiating all derivations. Production rules replace variables with strings of variables and terminals, enabling systematic string generation. The empty string (epsilon) terminates derivations. Grammars generate languages by deriving all strings from the start symbol through production rule applications. A key example demonstrates generating the language a^n b^n using productions S → aSB and S → ε, producing strings like ab, aabb, aaabbb. Multiple production rules for a single variable enable diverse string generation while maintaining structural constraints, such as equal numbers of a's and b's in all generated strings.