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.

  • $\begingroup$ 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) ? $\endgroup$ – Link L Feb 29 '20 at 3:47
  • $\begingroup$ @LinkL, that is another question. State it as such. $\endgroup$ – vonbrand Feb 29 '20 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.