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 ).

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

But Sipser does not seem to clarify if ALLCFG is also not turing-recognizable. Since ¯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


Source : Link , Question Author : Link L , Answer Author : Community

Leave a Comment