decidability of CFL emptiness and finiteness

Two basic questions about a grammar can be answered by algorithm, every time. EMPTINESS asks: does this context-free grammar generate ANY string at all, or is its language empty? FINITENESS asks: does it generate only finitely many strings, or infinitely many? Both are DECIDABLE — there is a procedure that always halts with the correct YES or NO. You never have to wonder; you can just compute.

Emptiness is solved by a simple marking process that finds the GENERATING variables. Mark every terminal as generating. Then repeatedly mark a variable A as generating whenever some rule A -> (right-hand side) has all of its right-hand symbols already marked. Keep going until nothing new gets marked — this stops because there are only finitely many variables. The language is NON-empty exactly when the START symbol ends up marked (it can reach an all-terminal string); the language is empty when it does not. Finiteness is then decided on the trimmed grammar (after removing useless symbols): build the dependency graph where A points to B if some rule of A uses B, and check for a CYCLE that can actually be reached from the start and can actually produce terminals. A usable cycle means a variable can be re-entered to make ever-longer strings, so the language is INFINITE; no such cycle means FINITE.

These decidable questions are the practical backbone of grammar tools — a parser generator can warn you that a nonterminal generates nothing (a likely bug) or that a sub-language is unexpectedly infinite. They also mark the boundary line: emptiness, finiteness, and membership are the decidable trio for context-free languages, and just past them lie the undecidable questions (equivalence, ambiguity, universality) that even this modest model cannot escape.