# Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e

An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $$TM$$ to recognize whether a $$CFG$$ (or a type 2 grammar) generates $$\Sigma^*$$, where $$\Sigma$$ is the alphabet. Call this language $$CFG_{all}$$

But the above language is also not computably enumerable. There can be a reduction from $$CFG_{all}$$ to $$\bar{A_{TM}}$$, where $$\bar{A_{TM}}$$ is the language s.t. the input $$TM$$ does not accept any input. $$\bar{A_{TM}}$$ is not computably enumerable.

But could we say that whether or not a type 3 grammar generates $$\Sigma^*$$ is also not c.e. ? (since type 3 grammars are a subset of context-free grammars). While it is true that a finite automaton can recognize $$\Sigma^*$$, this language is different right from whether a type 3 grammar generates $$\Sigma^*$$?

Just to clarify the source of my confusion, in summary, it is decidable for a $$TM$$ to decide whether a pushdown automaton recognizes $$\Sigma^*$$ or accepts any input, but it is not decidable or even computably enumerable for a $$TM$$ to recognize that a CFG generates $$\Sigma^*$$. Similarly, it is decidable for a $$TM$$ to check if a finite automaton accepts $$\Sigma^*$$, but it may not be decidable for a $$TM$$ to check if a type 3 grammar generates $$\Sigma^*$$. It's somehow the difference between recognizing and generating.

EDIT: apparently for a pushdown automaton to recognize $$\Sigma^*$$ is not decidable

To see if a type 3 grammar (regular) generates $$\Sigma^*$$ just build the minimal DFA accepting the language, and check if it is just initial = final state, with loop on all symbols. All constructions involved are effective.
• thanks, I saw the error in my question above (marked EDIT)... but just curious, do you know why a type 3 grammar cannot simulate computation histories while a $CFG$ can (or should this be another question in cs stack exchange) ? Feb 29 '20 at 3:47