Lecture
CYK algorithm
Description
This lecture covers the Cocke-Younger-Kasami (CYK) algorithm, which efficiently computes syntactic interpretations of sequences using chart parsing. It explains the principles of CYK, including the conversion of context-free grammars into Chomsky Normal Form (CNF) and extended CNF. The lecture also delves into the organization of syntactic analysis using a chart and the complexity analysis of the algorithm. Additionally, it discusses the challenges of exponential complexity and the bottom-up chart parsing technique to overcome CNF constraints.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.