the CFG emptiness problem

Step up one rung of the Chomsky hierarchy, to context-free grammars. A grammar is a set of rewriting rules — like S -> aSb or S -> ε (epsilon) — that you apply starting from a start symbol to spin out strings of terminals. The emptiness question asks: does a given grammar generate ANY terminal string at all, or does every attempt fizzle out before reaching a finished string? As a language, E_CFG = {G : G is a CFG and the language of G is empty}. As with DFAs, you do not test infinitely many derivations; you analyse the grammar's symbols.

The decision procedure is a marking process that discovers which symbols are 'generating' (can eventually be rewritten into a string of terminals only). Start by marking every terminal symbol as generating (a terminal is already a finished string). Then repeat: for any rule A -> X1 X2 ... Xk whose entire right-hand side is already marked generating, mark its left-hand variable A as generating too. Keep sweeping the rule list until a full pass marks nothing new. This must terminate because there are only finitely many symbols to mark. At the end, the grammar's language is non-empty if and only if the start symbol got marked as generating. So accept G into E_CFG exactly when the start symbol is NOT marked.

Thus E_CFG is DECIDABLE. This continues the story that the lower rungs of the hierarchy are algorithmically tame: just as DFA emptiness reduces to reachability in a finite state graph, CFG emptiness reduces to a finite fixed-point marking over the grammar's symbols. The same generating/reachable marking machinery is exactly what grammar simplification uses to strip out useless symbols, and emptiness testing is a building block in deciding other grammar properties. The honest contrast for later: while emptiness is decidable for CFGs, EQUIVALENCE of two CFGs is not.