Implementation and Analysis of the CYK Algorithm for Context-Free Grammar Recognition
Algorithmic Complexity, Probabilistic Extensions, and Theoretical Boundaries
An end-to-end study of the Cocke-Younger-Kasami (CYK) parsing algorithm: a deterministic parser built from first principles with a measured cubic-time complexity profile, a probabilistic Viterbi extension that recovers the most likely parse tree under ambiguity, and Pumping-Lemma proofs that establish the formal boundary of context-free recognition.