Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
CYK Algorithm for Parsing General Grammars
This lecture covers Chomsky's classification of grammars, including type 0, type 1, type 2, and type 3 grammars. It explains the challenges of parsing general grammars, such as ambiguity and the need for dynamic programming. The instructor demonstrates the CYK algorithm for parsing general grammars, focusing on Chomsky Normal Form and the steps involved in the algorithm. The lecture also discusses balanced parentheses grammar and the conversion to Chomsky Normal Form. It concludes with the analysis of the number of parse trees for a given word and the importance of CNF in simplifying grammar rules.