undecidability of whether a CFL equals Sigma-star
/ Sigma: SIG-muh /
Here is another question that sounds almost trivial yet is impossible to decide. Given a context-free grammar over an alphabet Σ (Sigma), does it generate ABSOLUTELY EVERY string — is its language equal to Σ* (Sigma-star), the set of all strings over the alphabet? This is the UNIVERSALITY problem, and for context-free languages it is UNDECIDABLE. There is no algorithm that always correctly answers 'yes, it generates everything' or 'no, it misses something'.
Why is missing-nothing so hard when emptiness (generating nothing) was easy? Emptiness asks whether there EXISTS a generated string, which a finite marking process settles. Universality asks whether ALL strings are generated, which secretly forces you to reason about every string that is NOT generated — the COMPLEMENT of the language. And the context-free languages are not closed under complement, so the complement may not even be context-free; the friendly tools (CYK, emptiness checking) no longer apply. The impossibility is proved by encoding the halting computations of a Turing machine: one builds a grammar whose language is exactly the strings that are NOT valid accepting computation histories, so the grammar generates Σ* if and only if the machine accepts nothing — a question already known to be undecidable.
This problem is the hub of several related undecidable questions: whether two context-free languages have empty intersection, whether a context-free language equals a given regular language, and whether a context-free language is actually regular are all undecidable too, and several reduce to or from universality. The pattern to remember: for context-free languages, 'does it generate SOMETHING' is decidable, but 'does it generate EVERYTHING' is not — the leap from existence to universality is the leap into undecidability.
For a DFA, universality is easy: complement it (flip accept states) and test emptiness. For a context-free grammar that trick fails because complement may leave the family. So you cannot, in general, decide whether a CFG generates all of Σ* — nor whether two CFLs intersect, nor whether a CFL is regular; these are all undecidable.
Existence (emptiness) is decidable; universality (generates everything) is not — complement is the lost tool.
Contrast with regular languages, where universality IS decidable (complement then test emptiness). The CFL case fails precisely because CFLs are not closed under complement.