Taki pomysł, proszę o weryfikację.
Najpierw z produkcji tworzę sobie graf (dwudzielny), w sposób następujący:
Niech na początku V = N, czyli wierzchołkami są nieterminale.
Niech N → P_1, N → P_2, \ldots, N → P_k będą wszystkimi produkcjami wychodzącymi z nieterminala N.
Wówczas tworzę wierzchołki etykietowane N_1, \ldots, N_k (dokładam k nowych) i rysuję krawędzie N → N_i.
Natomiast z N_i rysuję krawędzie prowadzące do wierzchołków etykietowanych nieterminalami występującymi w P_i.
Łatwo zauważyć, że jeżeli N –> w, to \exists i.N → N_i \wedge \forall M.N_i → M \Rightarrow M →* w' dla pewnych słów w'.
Teraz algorytm: w każdym momencie mam listę nieterminali N, z których da się wyprodukować słowo. Inicjuję ją, a następnie:
1. wybieram pewien N z tej listy 2. przeglądam krawędzie wchodzące do N. Niech M_i → N. Jeżeli

Gramatyka to u mnie (V,\Sigma,P,S).

Zdefiniujmy sobie f(X):V→\mathbb{B} = True, jeśli \exists w \in \Sigma^* . X \Rightarrow^* w\ | False\ wpp.

Jak łatwo zauważyć, f(A)\ \mathit{wtw}\ \exists B_1B_2\ldots B_k.(A\rightarrow B_1B_2\ldots B_k)\in P \wedge \forall i\ .\ f(B_i).

f(x) = True,\ gdzie x\in \Sigma^*

Chcemy, aby f(S) = True.

I TERAZ rysujemy sobie graf dwudzielny tak jak napisano powyżej: po lewej zmienne i terminale, po prawej symbole oznaczające wszystkie prawe strony wszystkich produkcji. Krawędź w prawo oznacza „yields” (Sipser), krawędź w lewo oznacza „zawiera w sobie wystąpienie zmiennej”. A dalej to już widać: przy każdym {bycie z prawej} piszemy liczbę oznaczającą ilość krawędzi z niego wychodzących. Następnie z każdego terminalu rozdajemy po jednym punkcie jego poprzednikom. Byty z prawej, które dostały tyle punktów, ile potrzebowały, wciągają do gry następne symbole, dla których powtarzamy rozdawanie punktów itd., aż do osiągnięcia punktu stałego. Jeśli S został wciągnięty do gry, zwróć True. Else → False.