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)$.