CYK Parsing Algorithme pour les grammaires générales

Cette séance de cours couvre la classification des grammaires de Chomsky, y compris le type 0, équivalent aux machines de Turing, le type 1 avec les machines de Turing O (n)-espace, le type 2 grammaires sans contexte, et le type 3 grammaires régulières. Il introduit l'algorithme d'analyse CYK pour des grammaires sans contexte, discutant de sa nature déterminable, de meilleures possibilités de complexité et d'adaptations pratiques. La séance de cours explique comment l'algorithme CYK peut gérer l'ambiguïté dans les grammaires générales, l'importance de les analyser et les deux étapes principales de l'algorithme: transformer la grammaire en Chomsky Normal Form et analyser l'entrée en utilisant la programmation dynamique. Il approfondit également la grammaire des parenthèses équilibrées, en analysant les entrées étape par étape, et fournit une implémentation Scala de l'algorithme CYK.