Développement #761

Titre : Algorithme d'Earley

Contenu : L'algorithme d'Earley sert à vérifier si un mot $w$ appartient au langage d'une grammaire $G$. Il le fait en temps $O(\lvert w\rvert^3)$, comme l'algorithme CYK, mais on peut de plus prouver que la complexité n'est que de l'ordre de $O(\lvert w\rvert^2)$ dans le cas d'une grammaire non ambigüe, et même linéaire si la gramaire est rationnelle, ce qui en fait un des meilleurs algorithmes connus en pratique !

Créé le : 23/07/2026 12:42

Mis à jour : 23/07/2026 12:42