Développement : Algorithme CYK

Détails/Enoncé :

Soit $G$ une grammaire donnée sous forme normale de Chomsky. Alors, étant donné un mot $w$, on peut tester si $w \in L(G)$ en temps $O(|w|^3)$.

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :

Références utilisées dans les versions de ce développement :

Langages formels, Calculabilité et Complexité, Carton (utilisée dans 19 versions au total)
Le Langage des machines, Floyd, Beigel (utilisée dans 7 versions au total)