section_heading: Neodlučivi problemi
paragraph_text: Iako su neke operacije nad kontekstno neovisnim gramatikama odlučive zbog njihove ograničene moći, KNG imaju nekih zanimljivih neodlučivih problema. Jedan od najjednostavnijih i najpoznatijih jest problem odlučivanja generira li KNG jezik svih nizova znakova. Može se demonstrirati redukcija na ovaj problem iz dobro poznatog neodlučivog problema određivanja prihvaća li Turingov stroj neki pojedinačni ulaz. Ta redukcija koristi koncept povijesti izračuna, niz znakova koji u cijelosti opisuje tijek izračuna (komputacije) Turingovog stroja. Možemo konstruirati KNG koja generira sve nizove znakova koji nisu prihvatljive povijesti izračuna za neki pojedinačni Turingov stroj za neki pojedinačni ulaz, te će stoga KNG generirati sve nizove znakova samo ako stroj ne prihvaća taj ulaz.