Rozstrzygalne są takie problemy jak: czy dane słowo należy do danego języka (algorytm CYK wykonuje ten test w czasie ), czy istnieje jakiekolwiek słowo, które należy do danego języka, czy do danego języka należy co najmniej słów, czy dany język zawiera nieskończenie wiele słów.
Nierozstrzygalne problemy to natomiast m.in.: czy istnieje jakiekolwiek słowo, które nie należy do danego języka, czy dane dwa języki są równe, czy jeden język bezkontekstowy jest podzbiorem drugiego, czy istnieje słowo wspólne dla danych dwóch języków, czy dany język jest jednoznaczny, czy dana gramatyka jest jednoznaczna.
Dowód nierozstrzygalności istnienia wspólnego słowa Pytanie czy przekrój 2 języków jest niepusty można zredukować do problemu odpowiedniości Posta – niech oznacza -tą parę słów w systemie Posta. Stwórzmy dwa języki bezkontekstowe i dla każdego odpowiadającego parze słów w systemie Posta,
gdzie są nowymi symbolami terminalnymi, niewystępującymi w żadnym ani
Wygenerowane słowo języka składa się ze słowa wygenerowanego przez pierwszy język systemu Posta, oraz (odwróconego) znaczenia tego słowa: