I know it's undecidable, but how to prove it? Edit: It seems my description wasn't clear enough, the problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.