Algorithme CYK
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)$.
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 9 | Algorithmique du texte. Exemples et applications.2022 |
Utilisateur : Gayral
Références :
Utilisateur : Timothée
Références :
Langages formels, Calculabilité et Complexité - Carton
Le Langage des machines - Floyd, Beigel