# Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $$ALLCFG$$ is an undecidable language (where $$ALLCFG$$ means that $$G$$ is a $$CFG$$ that generates $$\sum ^*$$).

In his textbook, there is a polynomial reduction from $$\bar{{ATM}}$$ (complement of $$ATM$$, where $$ATM$$ is the language that a $$TM$$ accepts input string $$w$$) to $$ALLCFG$$, where the reduction works by mapping $$\sum ^*$$ to all non-accepting configurations, i.e. if there is an accepting configuration from $$G$$, then $$G$$ does not generate $$\sum ^*$$.

But Sipser does not seem to clarify if $$ALLCFG$$ is also not turing-recognizable. Since $$\bar{ATM}$$ (a non computably enumerable language) polynomially reduces to $$ALLCFG$$, does this mean that $$ALLCFG$$ is also not computably enumerable? i.e. not turing-recognizable.

Which brings me to my main quesiton -- if $$ALLCFG$$ is indeed not-turing recognizable, then its complement should be turing recognizable since it would in turn reduce to $$ATM$$ -- but how should this language be phrased?

P.S. It could not be whether a $$CFG$$ generates a string $$s$$ since this language is decidable, but $$ATM$$ is turing-recognizable only and not decidable

• ALLCFG is not recognizable - by reduction from $\overline{ATM}$ - but its complement is recognizable, using the algorithm deciding whether a word belongs to the language of a CFG. – Yuval Filmus Dec 2 '18 at 8:07
• Thanks , although deciding whether a word belongs to a CFG should be a decidable problem right?... But if it is decidable then its complement should be turing recognizable which in this case isn't... – Link L Dec 2 '18 at 9:07
• These are not the same problems - there’s a step missing here. – Yuval Filmus Dec 2 '18 at 17:14